"Fictitious" is a much more pejorative term, suggesting a deliberate or knowing falsehood. Legendary builds on the definition you provide -- if something placed in time 1500 years ago were not remarkable in some fashion, it never would have been written down. But legends develop sometimes by accretions of fictions on top of an actual fact, or sometimes by embellishment of something originally misunderstood. If I write a fake genealogy today it is a fiction and if I do it for money, it's a fraud. But if someone did it 300 years ago, and the material has been treated as fact and found its way into numerous other genealogies, then it has become a legend, and disentangling truth from fiction in each affected genealogy becomes a challenge.
I'm a firm believer that you have to document what is false in order to protect what is true, but until you know for sure, "legend" seems like a more neutral way of saying, "this is out there, and a lot of people repeat it, but we're not sure what it is."