Middle English, representing the merger or mutual influence of two words, one from Old English, one from an Old French form of the same Germanic word, and both ultimately from a PIE root meaning "cattle."

The Old English word is feoh "livestock, cattle; movable property; possessions in livestock, goods, or money; riches, treasure, wealth; money as a medium of exchange or payment," from Proto-Germanic *fehu (source also of Old Saxon fehu, Old High German fihu, German Vieh "cattle," Gothic faihu "money, fortune"). This is from PIE *peku- "cattle" (source also of Sanskrit pasu, Lithuanian pekus "cattle;" Latin pecu "cattle," pecunia "money, property").

The other word is Anglo-French fee, from Old French fieu, a variant of fief "possession, holding, domain; feudal duties, payment" (see fief), which apparently is a Germanic compound in which the first element is cognate with Old English feoh.

Via Anglo-French come the legal senses "estate in land or tenements held on condition of feudal homage; land, property, possession" (c. 1300). Hence fee-simple (late 14c.) "absolute ownership," as opposed to fee-tail (early 15c.) "entailed ownership," inheritance limited to some particular class of heirs (second element from Old French taillir "to cut, to limit").

The feudal sense was extended from landholdings to inheritable offices of service to a feudal lord (late 14c.; in Anglo-French late 13c.), for example forester of fe "a forester by heritable right." As these often were offices of profit, the word came to be used for "remuneration for service in office" (late 14c.), hence, "payment for (any kind of) work or services" (late 14c.). From late 14c. as "a sum paid for a privilege" (originally admission to a guild); early 15c. as "money payment or charge exacted for a licence, etc."

Proto-Indo-European root meaning "to lie down, lay."

It forms all or part of: allay; anlage; belay; beleaguer; bylaw; coverlet; fellow; lager; lair; law; lawful; lawless; lawsuit; lawyer; lay (v.) "to cause to lie or rest;" ledge; ledger; lees; lie (v.2) "rest horizontally;" litter; lochia; low (adj.) "not high;" outlaw; scofflaw; stalag; vorlage.

It is the hypothetical source of/evidence for its existence is provided by: Hittite laggari "falls, lies;" Greek lekhesthai "to lie down," legos "bed," lokhos "lying in wait, ambush," alokhos "bedfellow, wife;" Latin lectus "bed;" Old Church Slavonic lego "to lie down;" Lithuanian at-lagai "fallow land;" Old Irish laigim "I lie down," Irish luighe "couch, grave;" Old English licgan "be situated, have a specific position; remain; be at rest, lie down."

"close friend, roommate, one who shares a bed with another," mid-15c., from bed (n.) + fellow (n.). Also (late 15c) "concubine." Earlier in the "close companion" sense was bed-fere (early 14c.). Old English had simply bedda. Bedsister "husband's concubine" is recorded in Middle English (c. 1300).

an attempt at a phonological spelling of a casual pronunciation of fellow (n.), attested by 1864 (as fellah). Feller, along the same lines, is recorded by 1825. Earlier, Pope rhymes fellow with prunella ("Essay on Man," epistle IV).

1610s, an attempt to translate the sense of Latin compassio and Greek sympatheia. See fellow (n.) + feeling (n.). It yielded a back-formed verb, fellow-feel in 17c., mercifully short-lived.

c. 1200, feolahschipe "companionship," from fellow + -ship. The sense of "a body of companions" is from late 13c. The meaning "spirit of comradeship, friendliness" is from late 14c. As a state of privilege in English colleges, from 1530s. In Middle English it was at times a euphemism for "sexual intercourse" (carnal fellowship).

To fellowship with is to hold communion with; to unite with in doctrine and discipline. This barbarism now appears with disgusting frequency in the reports of ecclesiastical conventions, and in the religious newspapers generally. [Bartlett, "Dictionary of Americanisms," 1848]

But Chaucer and Wycliffe used it as a verb in Middle English, "to have fellowship with."

also play-fellow, "companion in amusements or sports," 1510s, from play (n.) + fellow (n.).

Old English welig "willow," from Proto-Germanic *wel- (source also of Old Saxon wilgia, Middle Dutch wilghe, Dutch wilg), probably from PIE root *wel- (3) "to turn, revolve," with derivatives referring to curved, enclosing objects. The change in form to -ow (14c.) paralleled that of bellow and fellow. The more typical Germanic word for the tree is represented by withy.