When historians write about the roots of hair removal, they usually describe an enjoyable bathing ritual in which luxurious unguents are languidly applied to the skin. Wine is often involved, as are solicitous and comely attendants.But she goes on to discuss a less romantic myth, or at least legend:
The modern reality bears no resemblance to such romantic myths. ...
... In Plucked: A Social History of Hair Removal by Rebecca Herzig, the gender studies professor looks at Western leg-shaving habits across racial, ethnic and regional lines. The book explores the extremes women go to in pursuit of smooth skin, recounting how a popular 19th-century depilatory powder, Dr. Felix Gouraud’s Poudres Subtile for Uprooting Hair, marketed itself as being based on a formula used by the Queen of Sheba. Herzig reminds readers that in some ancient versions of the Quran and the Hebrew Bible, King Solomon summons demons to make núra, an arsenic-laced quick lime depilatory to apply to the queen’s hairy legs (other versions of the story suggest the substance was made of boiled honey and turpentine and rolled onto the skin).The story of the Queen of Sheba's hairy legs may be hinted at in the Qur'an, but it does not appear in the Hebrew Bible. Rather, we know it from later Muslim and Jewish legends. I have collected some background here (final paragraph of post).
UPDATE: Also, lots more on the (perhaps) historical and the legendary Queen of Sheba here, here, here, and links