Fact and fairy aren't etymologically related, but John Lawler's answer is probably not correct when it states that fairy is related to Latin fidēs. According to regular vowel changes, fidēs corresponds to the French word foi 'faith'. The Old French form fei, which is the source of an obsolete English word "fay" meaning "faith", looks a bit more similar to fairy in form, but as far as I know was not used with a "fairy"-related meaning.
The usual etymology given for French fée 'fairy' (in Old French also spelled fae or faie) is instead that it is related to Latin fātum 'fate, doom' via the plural form fāta, which you mention. This plural form is supposed to have been reinterpreted as a singular feminine noun, which was a common development for Latin neuter plural forms. Regular Latin-to-French sound changes get us from fāta to faie/fae/fée.
Fātum/fāta in turn is supposed to come from the Latin verb for 'speak', which Wiktionary says is from a PIE root that is reconstructed as *bʰeh₂-. This only shares the first consonant in common with *bʰeydʰ. (The vowel "e" included in the citation forms of most Proto-Indo-European roots is typically not a distinctive part of the root, but can be replaced according to the system of "ablaut" or "vowel gradation"). And it has nothing in common with the root *dʰeh₁.
The path from fātum to fairy is somewhat complicated; I go over the hypothesized intermediate steps in my answer here: Etymology of “fairy”