overshoe (n.)

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.), oversmall (mid-13c.), overshort, etc.

Middle English sho, "low-cut covering for the human foot," from Old English scoh, from Proto-Germanic *skokhaz (source also of Old Norse skor, Danish and Swedish sko, Old Frisian skoch, Old Saxon skoh, Middle Dutch scoe, Dutch schoen, Old High German scuoh, German Schuh, Gothic skoh). No known cognates outside Germanic, unless it somehow is connected with PIE root *skeu- "cover" (source also of second element in Latin ob-scurus).

The old plural form shoon lasted until 16c. The meaning "metal plate or rim nailed to the hoof of a horse or beast of burden to protect it from injury" is attested from c.1300. The distinction between shoe and boot (n.) is attested from c. 1400.

To stand in someone's shoes "see things from his or her point of view" is attested from 1767. Old shoe as a type of something worthless is attested from late 14c.

Shoes tied to the fender of a newlywed couple's car preserves the old custom (mentioned from 1540s) of throwing an old shoe at or after someone to wish them luck. Perhaps the association is with dirtiness, on the "muck is luck" principle.