The spelling could be "malihini." (At least, Google gives 49,900 hits on "malihini" but only 16,300 on "malahini.") Google gives no hits on "melancholy malahini" or "... malihini" (as quoted phrases).
The Hawaiian Hula Archives—which looks pretty authentic—has 64 occurrences of "malihini" but none of "malahini."
It lists hundreds of songs, including about 200 "hapa-haole" songs, but none of them have the word "melancholy" in the title. I could find only one song that has "malihini" in the title: MALIHINI MELE.
Allmusic.com lists: MALIHINI MALIHINI HULA MALIHINI MELE MALIHINI O WAIMEA PUA MALIHINI ...and has several sound samples. You might try listening to see if any of them sounds like the song you want.
Another approach might be to try to identify the program you were watching.