Norman Cazden provides some interesting historical notes in Folk Songs of the Catskills, in his discussion of another song with the same general tune, "The Prisoner's Song". In particular, he mentions a five-verse localized version of "Red River Valley" from Iowa, with dates 1879 and 1885. The Kerrigan derivation has by now been soundly disproved, though it remains perhaps the most famous "alternate version".

Fowke posited that the song arose during the Red River resistance (later characterized a rebellion) of 1869-1870 in Manitoba, Canada, led by Louis Riel. Another poster mentioned that "We Will Walk..." was published only a few years after the rebellion, and could easily have lent its tune to a new song dealing with the earlier event. Though it's also possible that Peacock borrowed a popular tune for the chorus of his music, and his credit properly only applies to the verse tune and arrangement. And it's possible the text and tune were written independently and were only married some time later.

In short, the precise provenance remains conjectural, though it's generally accepted that the lyrics arose in Manitoba in the 1870's, possibly as early as 1869. It had spread to other parts of Canada by the time of the North-West Rebellion (1885, the second Riel rebellion) and was already being adapted in the U.S. by 1879. The tune dates at least from 1874.