I'm glad you recommended Paul Heinegg's book and website, as his work has established great documentation of African Americans free in the colonial period. He noted that 80% of free people of color on the censuses from 1790-1810 in NC were descendants of those colonial families. He traced them through every kind of records.
In addition to slaves being freed by the British for service, the two decades after the Revolutionary War were a period when a number of slaveholders, especially in the Upper South, freed slaves - as someone mentioned, often in deeds or wills. Quakers and Moravians worked hard to persuade slaveholders to practice manumission.
91% of blacks in Delaware were free by 1860, and 49.7% of blacks in Maryland. (Peter Kolchin, American Slavery)