Looking at these three resources, you would be wrong with your assumption that the word is not related to fehlen:
Kurzes deutsches Wörterbuch - Eintrag empfehlen
Empfehlen, Kl I, aus emp, ahd. [alt-hochdeutsch] in, und fehlen, ahd. velahan, der Sorge, Gunst von Jemandem befehlen; [...]
Vokalspalter Blog - Eintrag Empf-
Warum schreibt man empfinden, empfangen und empfehlen mit empf- und nicht mit entf- wie z.B. entfachen, entfalten oder entfernen? Empfinden war schliesslich auch einmal ent-finden (also ‘herausnehmen’ oder eben ‘wahrnehmen’), empfangen einmal ent-fangen (‘fangen’ im Sinne von ‘nehmen’) und empfehlen einmal ent-fehlen (hat jedoch nichts mit fehlen zu tun, sondern ist mit befehlen verwandt; fehlen kommt von altfranzösisch faillir [edit 20.10.14, merci Christoph] (sic)
(with additional given source of Quelle: Kluge, Friedrich (2011): Etymologisches Wörterbuch der deutschen Sprache. Bearbeitet von Elmar Seebold. 25., durchgesehene und erweiterte Auflage (1. Auflage: 1883). Berlin: De Gruyter.. The blog author is apparently a linguistic student, for what that's worth)
Also, a very fun and useful source:
Indo-European etymology - Entry fehlen
Proto-IE: *ēg'-
Meaning: to say, to tell
Tokharian: A,B āks- 'announce, proclaim, instruct, recite' (PT *āks-) (Adams 38-39)
Armenian: asem `sage'
Old Greek: *ēg'-t: hom. ipf. ē̂ er sprach' (sekund. nachhom. Neubildungen ipf. 1 sg. ē̂n, prs. 1 sg. ēmí); pf. (prs.-Bed.) án-ōga
befehlen' (sekund. prs. anṓgō)
Latin: aiō, aī̆s bejahen, behaupte, sagen'; adagiō
Sprichwort', prōdigium Vorzeichen', pl. axāmenta
carmina Saliaria', indigitāre anrufen', Aius Locūtius
der Gott, der durch seine Stimme das Herannahen der Gallier verkündete'
Other Italic: Umbr aiu `oracula'
Russ. meaning: говорить
This last resource is a fun rabbit hole to dive down into. As is:
Heinrich Tischner Etymologie - Entry fehlen and Ibid. - Entry ent-
That one can't be easily copy-pasted as it has a lot of links for further research.