"travel on foot," c. 1200, a merger of two verbs, 1. Old English wealcan "to toss, roll, move round" (past tense weolc, past participle wealcen), and 2. wealcian "to roll up, curl," from Proto-Germanic *welk- (source also of Old Norse valka "to drag about," Danish valke "to full" (cloth), Middle Dutch walken "to knead, press, full" (cloth), Old High German walchan "to knead," German walken "to full"), perhaps ultimately from PIE root *wel- (3) "to turn, revolve."
The shift in sense is perhaps from a colloquial use of the Old English word or via the sense of "to full cloth" (by treading on it), though this sense does not appear until after the change in meaning. In 13c. it is used of snakes and the passage of time, and in 15c. of wheeled carts. "Rarely is there so specific a word as NE walk, clearly distinguished from both go and run" [Buck]. Meaning "to go away" is recorded from mid-15c. Transitive meaning "to exercise a dog (or horse)" is from late 15c.; meaning "to escort (someone) in a walk" is from 1620s. Meaning "move (a heavy object) by turning and shoving it in a manner suggesting walking" is by 1890. To walk it off, of an injury, etc., is from 1741. Related: Walked; walking.