Where does the idea that the fae have wings come from?
Its rooted in the theater, actually, as a quick device to show an audience that an actor/actress was a fairy. We can see examples of this usage from the 18th century. From there it entered the public consciousness and became especially popular in Victorian artwork, and has become ubiquitous today for many people.
The concept itself likely grew out of the depiction of angels and devils in artwork, as well as human souls, that showed them winged. This would have naturally lent itself to the need for a visual aid to help an audience identify a character as Otherworldly.
Prior to this we do not see fairies in artwork with wings, nor do we hear them described in stories as having wings; when they fly in folklore it is through the use of magic, often by turning an object into a horse that can move through the air or simply by what we might call levitation. Shapeshifting is another main method fairies in folklore use to fly.