It was insinuated by Ardra in this episode that Fek'lhr is roughly the Klingon version of a devil. This is probably not a proper equivalent however as Kang said in TOS: "Day of the Dove" that Klingon beliefs do not recognize a devil archetype.
In Star Trek Online, the Fek'Ihri strongly resemble Fek'lhr. They are real creatures from outside normal space that attacked the Klingon empire in ancient times, and commanded by Molor during his reign. They have now returned to invade the Empire. It may have inspired the legend. Fek'lhr himself appears as the final enemy of the Fek'Ihri campaign. After scanning Fek'lhr's corpse, the player's Bridge Officers will notice traces of Hur'q technology.