As @FumbleFingers indicated, at the core of the difference between the two is a creative preference.
From my experience, here's what the two options imply (to me, at least), admittedly exaggerating to illustrate nuance:
A sword that uses fire as its main means of functioning or source of
"Sword of Fire"
The sword that is the essence and embodiment of the great element of fire.
An egg that uses lightning as its main means of functioning or source
"Egg of Lightning"
The egg that embodies the great element of lightning and endows this elemental power to whoever possesses it
In other words, in these cases where a noun modifies another noun in this type of context, going out of one's way to use "of" adds an air of (purposeful) majesty, grandeur, power, etc. "Of" also tends to suggest that the object is the only of its kind, consistent with suggested majesty/grandeur.