I've never heard the
Paul McCartney song. So I don't have the same association as you.
Willow makes me think of a woman destined to misfortune and sadness.
Willow can only be the name of a character in some Greek tragedy.
My feelings may be influenced by the weeping willow. I would much prefer the "happier"
Willa, but then
Willa doesn't flow well with
Melissa.