There is a Melisandre mentioned in Don Quixote by Miguel de Cervantes, may you anglosaxons had nor read it, but in this novel, the spanish writer who lived during the XVI-XVII centuries makes a parody about medieval novels and epic songs about chivalry, King Arthur, the Holy Grial, Charlemagne and his knights, etc. stories that during his times were still very liked in Spain, in a passagge, While in an Inn, Don Quixote watches a puppet show about the "Rescue of Melisandre" an epic song about a princess named Melisandre who was taken as a captive by the muslimes, and his husband: Sir Gaiferos, a knight at Charlemagne's service who goes to rescue her, fighting great battles he alone against all the muslim army. I don't know if Martin have readed Don Quixote or, even, and more probably, the song reffered in the Cervantes' novel.