Early sources describe holding the hands in shashu, taking the appropriate mental attitude, and walking neither fast nor slow in a straight line before turning around and coming back. However, the texts on monastic rules that were available to Dogen when he was training just instruct practitioners to generally walk in a way appropriate for a temple and indicate that walking inside or under the eaves in one's free time is fine.
Dogen’s Bendoho describes something that sounds like our slow kinhin in relation to entering and leaving the zazen hall, not as something done between zazen periods. The hands are clasped together inside the sleeves, but nothing is mentioned about matching one's breathing to one's steps. The Hokyoki has more; that text describes what Dogen learned from his teacher Tendo Nyojo. It describes the slow walk with half steps and matched breathing, and Tendo Nyojo says he’s the only one who knows this practice. Again there is nothing about when and how long to do kinhin or its purpose or role as a practice.
Overall, there is nowhere near the detail about the posture or context of kinhin that Dogen provides about zazen, so we can’t really make a direct link between Dogen’s walking and our kinhin process. We also can’t link kinhin to what’s described in the Pali Canon. Even so, the two main points that Menzan makes in the Kinhinki are:
1) Kinhin is an old and orthodox practice of the Buddha himself, and
2) Tendo Nyojo somehow had preserved this neglected practice and taught it to Dogen face-to-face.
By putting together the old texts that have instructions, Menzan tried to show that he had restored the true ritual kinhin practice of the buddhas and ancestors. The actual result is that Menzan made something new out of fragments of unrelated texts scattered across time and space. He doesn’t refer to living examples of temples that do it this way, which is an interesting contradiction in the way the Kinhinki is created. On the one hand, it relies on various texts to establish the way kinhin should be done. On the other, a central theme in the Kinhinki is that Tendo Nyojo somehow preserved the practice and personally passed it down to Dogen and thus it’s a legitimate Soto practice.
Menzan wrote the Kinhinki in the style of Dogen teaching about zazen, and it’s now considered the basis for modern Soto Zen kinhin despite the lack of instruction about alternating it with zazen periods. It's also not clear whether the hand position he’s describing is isshu or shashu, and that’s relevant to Sanshin. Kodo Sawaki did isshu 揖手 during kinhin as we do now rather than shashu 叉手. His biography says only his lineage does isshu even in Japan. Also, the Kinhinki says one should stand without moving for a few minutes before starting to walk, whereas Sawaki Roshi began walking right away.
Uchiyama Roshi apparently said that that before Sawaki Roshi's time practitioners weren't sitting more than one period of zazen at a time and thus they didn't need to know about alternating this with kinhin. It seems that teachers who wanted to recreate the practice of kinhin studied relevant texts and interpreted them differently, leading to the various styles we see today.