The "candy" part of the phrase comes from Arabic qandi, "crystalized sugar," and likewise Persian kand (reborrowed later from Arabic as qand).
It seems likely that the Arabic and Persian words derive from Sanskrit khanda, "piece (of candied sugar)." It seems possible in turn that this Sanskrit word is a Dravidian borrowing; compare the Tamil word kantu, meaning "ball (of candied sugar)."
If you poke around on the Internet, you will find claims that the Arabic qandi has something to do with the island of Crete and sugar production there. This is a misunderstanding, however, probably prompted by the medieval Latin name for Crete, Candia (English "Candy"), which comes from the Arabic Khandaq, a place name having nothing to do with crystalized sugar.
The image below shows a cotton candy vendor in Tamil Nadu (photo by Abhijit at Flickr).
