According to Wiktionary, Galician, Catalan and Occitan have a word fada "fairy" and Italian has fata with the same meaning, which seems like a clear confirmation of a Vulgar Latin form *fata meaning "fairy". (And as tchrist points out, Spanish has hada, because it had a historical change of /f/ to /h/ in many contexts.) I don't know if there are any alternative explanations for this aside from a derivation from Latin fatum/fata.
The phonological development from fata > French fée is quite straightforward: intervocalic t was lenited and lost in French, word-final a was turned to schwa, represented by the letter "e", and stressed "a" was in many circumstances fronted and raised in French, here to /e/ "é", similar to the development of the past participle suffix "-é(e)" from Latin -ātus/-āta. (There are alternative spellings, some of which may correspond to slightly different vowels.) There are many other examples of these sound changes; e.g. Fr. chaîne < Lat. catena also shows the loss of intervocalic "t" and change of final "a" to "e".
I'm not sure how to explain the semantic development but it doesn't seem too far-fetched to me.
As you can see in the OED entry, the -ry part of fairy comes from the -ery suffix; French faerie/faierie/farie/féerie was an abstract noun referring to magic or the realm of the fairies, which seems to have developed in English into a collective noun and then finally the current singular meaning. The OED records earlier uses in English that were closer to the sense of the French word:
Enchantment, magic. Also: an instance of this; an illusion, a dream; a dazed or excited state of mind. Obs. [...]
a. A magical or enchanted land or domain; the (imaginary) realm or world of fairies (sense A. 3a); fairyland; = faerie n. 2. [...]
b. Chiefly with the. The supernatural or magical beings inhabiting such a realm; fairies (sense A. 3a) collectively. Cf. faerie n. 1b. Somewhat rare in later use.