Certain stones on Mount Carmel are so called. (See Stanley, Sinai and Palestine.) Similar formations are those called “The Virgin Mary's Peas” (q.v.). Compare also the Bible story of Lot's wife.
The story is that the owner of the land refused to supply the wants of the prophet, and consequently his melons were transformed into stones.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Elijah's Melons from Infoplease: