word-forming element meaning variously "above; highest; across; higher in power or authority; too much; above normal; outer; beyond in time, too long," from Old English ofer (from PIE root *uper "over"). Over and its Germanic relations were widely used as prefixes, and sometimes could be used with negative force. This is rare in Modern English, but compare Gothic ufarmunnon "to forget," ufar-swaran "to swear falsely;" Old English ofercræft "fraud."
In some of its uses, moreover, over is a movable element, which can be prefixed at will to almost any verb or adjective of suitable sense, as freely as an adjective can be placed before a substantive or an adverb before an adjective. [OED]
Among the old words not now existing are Old English oferlufu (Middle English oferlufe), literally "over-love," hence "excessive or immoderate love." Over- in Middle English also could carry a sense of "too little, below normal," as in over-lyght "of too little weight" (c. 1400), overlitel "too small" (mid-14c.), overshort, etc.
Old English steppan (Anglian), stæppan (West Saxon) "take a step," from West Germanic *stap- "tread" (source also of Old Frisian stapa, Middle Dutch, Dutch stappen, Old High German stapfon, German stapfen "step"), from PIE root *stebh- "post, stem; to support, place firmly on" (see staff (n.); source also of Old Church Slavonic stopa "step, pace," stepeni "step, degree"). The notion is perhaps "a treading firmly on; a foothold."
Transitive sense (as in step foot in) attested from 1530s. Related: Stepped; stepping. Originally strong (past tense stop, past participle bestapen); weak forms emerged 13c., universal from 16c. To step out "leave for a short time" is from 1530s; meaning "to go out in public in style" is from 1907. Step on it "hurry up" is 1923, from notion of gas pedal.