Though it's possible the use of Belinda in Italian literature is older, in England Melinda seems to be about as old as Belinda. For example, Aphra Behn's famous poem "The Coquette" is about a Melinda, and this was published around 1680, eight years earlier than the first English literary use of Belinda mentioned in the comments about Belinda on this site.
An English compound name using either Melissa (sweet) or Melanie (black/dark) in combination with Linda (serpent) and therefore meaning (black/dark serpent) or (sweet serpent).