Fenja er gen. plur. af feni, mose, [1] og Menja af mani, smykke, [2] der også kendes fra navnet på Frejas smykke Brisingamen.
Sagnet
Sagnet fortæller, at de var to jættepiger med enorme kræfter, og trælle for kong Frode, som tvang dem til at male guld og gode tider på kværnen Grotte. De gode tider mærkede søstrene dog ikke noget til, for kong Frode undte dem ikke mere hvile, end det tog "et vers at kvæde". Men søstrene tog hævn og fremmalede søkongen Mysing med en hær, der nedkæmpede kong Frode. Men søkongen handlede med salt, og han tog søstrene og Grotte om bord på sit skib, hvor han tvang dem til at male salt. Til sidst fik skibet overvægt af det meget salt og gik til bunds. Nede på havbunden kværner Grotte videre, og derfor, fortæller Snorri Sturluson, er havet salt.
Nyere version af sagnet
Nogle mener, at skibet gik til bunds i havet mellem Fanø og Mandø, fordi havet er særligt salt der, og fordi de to øers navne passer med de to søstres. Her møder man en anden version af Snorris sagn: Der var engang to skibe, som skipperne havde opkaldt efter de to jættekvinder, Fenja og Menja. Jættekvinderne havde en kværn, der kunne male guld, og to andre, der kunne male salt. De to skippere gjorde jættekvinderne en tjeneste og fik som belønning hver en kværn, der kunne male salt. Kværnene tog de ombord, malede salt og solgte det i forskellige havne. I en storm strandede de to skibe. Det ene på en sandbanke, der efter skibet fik navnet Menjø (Mandø), og det andet på en sandbanke, der efter det strandede skib fik navnet Fenjø (Fanø). [3]