Pound, "The Cambridge History of American Literature," p.505 assigns a War of 1812 origin; Newell, and Fowke (above) say it dates from the Revolutionary War.
The game has been collected from a wide area, but these collections are 20th c. "Marching Down to Old Berlin" has been collected in Oklahoma.

Fowke et al. provide a musical score with "Marching Down to Old Quebec."
A different score (Mass.) also is given by Harriet L. Wedgewood, JAFL, 1912, Vol. 25, No. 97, p. 271, but only the lines
We are marching down to Old Quebec
While the drums are loudly beating.
(repeated)
A third tune is given in Brown, North Carolina Folklore, vol. 5, p. 524, no date. There is a variant, "Marching Round the Levee," but it belongs with "Going In and Ot the Window."

I will try and find other early records.