Answers.com give one explanation for the origins of the legend....

'The Islamic legend of the Queen of Sheba, or Bilqis (alternatively, Balkis) as she is known in the Arabian tradition, stems from these short Jewish narratives. The story of the Queen's appearance at Solomon's court in the Islamic holy text, The Qu'ran, follows a thread similar to that of the Book of Esther.
In Chapter 27 of the Qu'ran, a messenger bird declared: "I have come to thee from Saba with sure tidings. I found a woman ruling over all of them; she has been granted everything and she has a wondrous throne. I found her and her worshipping the sun, instead of Allah." The passage further explains that Satan has led the queen and her subjects away from Allah, and Solomon, thinking to test this assertion, sends the bird back to the queen with a letter requesting confirmation of the bird's tale. Upon receiving the queen's response of extravagant gifts, Solomon is not satisfied and writes again, requesting her presence. The queen visits Solomon and, awed by his court, converts to the worship of Allah.

Arabian legends based on the Qu'ran embellish this story to include some speculation about the queen's descent from demons and later, her possible marriage to Solomon.

Solomon's advisors inform him that the queen has hairy legs; to discover the truth of this, Solomon constructs a palace with glass floors. The queen, believing the floor to be made of water, lifts her skirts, revealing her legs and feet.'

"later Moslem writers interpreted this physical peculiarity as showing that she was of jinn descent; they constructed a romantic history of her father's marriage to a jinn maiden. "