Apart from the army experience (Australian but similar to Joe Offer's, and also to be avoided) the only times I've sung while actually walking 'with intent' have been; 1 to "Alouette", when striding out down Swanston St (Melbourne), which probably doesn't really count as "singing while hiking", and 2 to "When Johnny comes marching home". This was usually the tune and words that best fitted the need to push the legs up a long and steep hill while carrying a 60lb pack.
I always sang it more or less under my breath, rather than "to" or "with" anyone, and it was more or less a "work" song. Somehow the minor key and those words didn't require much effort to sing, leaving the lungs and vocal tract able to give maximum effort to the legs and shoulders.