The cover of E. Nesbit's Melisande
Melisande (MELL-iss-ahnd, may-lee-SAHND) is the French variant of Amalswintha, and the inspiration for the English name Millicent, meaning "strong worker." There has been some confusion on the name's connection to Melissa, meaning "honey bee." There's a possibility that each spelling variation has a different origin - Melisande from Melissa and perhaps Melisande as cognate with Millicent, but that is speculation, and there could be absolutely no connection to Melissa at all. Melisende was a popular name in France in the Middle Ages. This name has quite the list of credentials, including a play, opera, and fairy tale.
Besides the play Pelléas and Mélisande by Maeterlinck, the opera by Debussy, and the fairy tale mentioned above, Melisande was the alias of a character in the Broadway show Bells are Ringing, a handmaid in the book Zuleika Dobson by Max Beerbohm, a character in The Golden Basket by Ludwig Bemelmans, a noblewoman in the Kushiel series by Jacqueline Carey, a character in Enid Blyton's Adventures of the Six Cousins, the title of a short story by E. Nesbit, and there was a princess character in the Rankin and Bass animated film called The Flight of Dragons. Currently hanging on a museum wall in Germany is the Melisande painting by Austrian painter Marianne Stokes. Comic book readers may recognize the name as Ra's al Ghul's wife in the Batman storyline.
Melisandre, the character from Game of Thrones, is not quite the same name. Although this spelling has been seen historically, author Martin typically uses names that are unique to his created world but slightly similar to historical names in the real world.
In real life, historical namesakes spelled their names Melisende (and Melicent). Melisende of Jerusalem was Queen of Jerusalem from 1131 to 1153, then acted as regent until 1161. Her parents, King Baldwin II of Jerusalem and the intriguingly named Morphia of Melitene, had quite a love story. When Baldwin was elected king, he was urged to divorce his wife and find someone more politically favorable for the time. He refused, and in a show of love he postponed his coronation day until she could be crowned queen alongside him. Melisende's marriage to Fulk was the opposite, as there was a continuous battle for her right to rule alongside him as an equal, although they did eventually settle their differences. It is said she was a very good mother. Melisende was named after her countess grandmother, Melisende of Montlhéry, a daughter of Guy I of Montlhéry. (Melisende de Coucy may be a descendent. This link has notes on a Melisende de Cantilupe as well.) Melisende's sister gave the name to her daughter, Melisende of Tripoli. She was written about in the verse drama La Princesse Lointaine by Edmond Rostand.
Melisende of Arsuf was Lady of Arsuf around the same time as Melisende of Tripoli, and both came from Crusader states. Not a lot is known about her life. If she is the same as Melisende of Arsur, widow of Thierry d'Orca and remarried to Jean Ibelin, we can place her second marriage at about 1209. She had a son named Baudouin (Baldwin) of Ibelin.
Melisende of Lusignan, Princess of Antioch's direct line died out when her daughter died with no heir. She came from Jerusalem as well.
Melisende de Picquigny was born between 1060 and 1090 in Saint Omer, France. Her son may have been the Latin Patriarch of Jerusalem who convened the Council of Nablus with Baldwin II, Melisende of Jersusalem's father.
None of the spelling options mentioned were used in the U.S. in 2016. Melisande registered a total of four times - 5 in 1947, 5 in 1960, 6 in 1972, and 5 in 2005. It is almost as rare in France today. I suspect it won't take long for Melisandre to get some use because of America's current love of Game of Thrones names.
On one last note, the medieval girl's name Elysande is very similar, and alternate forms of the name found in that time include Helisent/Helissent, Elysant, Helisende, Helysoune, and Helyssent.