Alert reader Jean-Sébastien Girard pointed me at the Trésor de la langue française, which supports the derivation from fehu, and usefully adds that the earliest citations for feudum don’t have the d: feus, feum— which makes it clear that the Latin words derive from fehu too.  The d is thought to have crept in from the semantically related alodum ‘property’. 

Oh lordy.  Googling alodum brought me to an 1850 law dictionary, which notes that “Blackstone considers it the same as odh al, in the Northern languages… with the syllables transposed, alodh; and hence signifying entire or absolute property.”  With the syllables transposed?  That’s getting into Edo Nyland territory.