The tune of Red River Valley/etc is nearly identical with that of a famous New Orleans jazz song, "We Will Walk through the Streets of the City," also recorded by the Carter Family and by Bllind Gary Davis (and others).

I have just yesterday, 22Jul2005, found sheet music for "We Will Walk in the Streets of the City" at the Library of Congress' American Memory site. See
http://hdl.loc.gov/loc.music/sm1874.14542

The words are by Rev. Mr. A. Flamman and the music by Dr. T. H. Peacock, copyright (U.S.) 1874. The chorus is definitely the "Red River Valley" tune.

1874 is only 4 years after the end of the Canadian Red River Rebellion. It seems quite plausible to imagine that when "Streets of the City" was published someone found its chorus tune attractive enough to use it for a song about the late rebellion. In this scenario, it would spread to other areas and be adapted as a cowboy song and as "Bright Sherman/Mohawk Valley."