Old English (and northern Middle English) had brim "sea, surf, pool, spring, river, body of water," of uncertain origin but probably unrelated, perhaps from the Germanic stem *brem- "to roar, rage." "It became obs. in ME.; but was perhaps used by Spenser" [OED].
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 ofer "beyond; above, in place or position higher than; upon; in; across, past; more than; on high," from Proto-Germanic *uberi (source also of Old Saxon obar, Old Frisian over, Old Norse yfir, Old High German ubar, German über, Gothic ufar "over, above"), from PIE root *uper "over."
As an adjective from Old English uffera. The senses of "past, done, finished; through the whole extent, from beginning to end" are attested from late 14c. The sense of "so as to cover the whole surface" is from c. 1400. Meaning "leaning forward and down" is from 1540s. The meaning "recovered from" is from 1929. In radio communication, it is used to indicate the speaker has finished speaking (1926).
Above expresses greater elevation, but not necessarily in or near a perpendicular direction; over expresses perpendicularity or something near it: thus, one cloud may be above another, without being over it. Over often implies motion or extension where above would not; hence the difference in sense of the flying of a bird over or above a house, the hanging of a branch over or above a wall. In such uses over seems to represent greater nearness. [Century Dictionary]
Phrase over and above (mid-15c.) is pleonastic, for emphasis. Adjective phrase over-the-counter is attested from 1875, originally of stocks and shares. To be (someone) all over "be exactly what one expects of (someone)" is by 1721.