Let's focus on this final phrase:
말해야 했었던 널 향한 사랑의 말이야
First off, see that
의 말이야 is a form of
that's what i'm talking about.
In other words,
사랑의 말이야 is then,
love is what I'm talking about.
Now, getting closer to your question surrounding
(아/어)야 했었던, let's first point out that everything in this phrase before
사랑 modifies that noun (which obviously means "love").
There are two modifying phrases for love:
Let's take the 2nd one first since it's easier:
널 향한 is just
to your direction, so the song is saying that love they're talking about is meant for/in the direction of "you/너".
Now for the trouble spot:
~던 - A reminisced past action or continued action from the past is stated
Here are some examples:
이 음악은 내가 자주 듣던 것입니다 - I used to listen to this music often.
여기 있던 책을 누가 가져 갔나요? - Who took the book that was here?
~았(었,였)던 - A past action more clearly conveyed as having completed
떠들썩 했던 방이 갑자기 조용해졌어요 - The classroom which was noisy suddenly quietened down.
3년 전에 해어졌던 친구에게서 전화가 왔습니다 - I got a phone call from a friend who left three years ago.
** examples from Korean Grammar for International Learners, Yonsei University Press, 1988
말해야 했었던 사랑
We've left out so far the
(아/어)야 해 portion of this, but that just means (as I think we already know) that one "must" do something.
To put all the pieces together then we have
말 + 해야 (하다) + 았(었,였)던 + 사랑
which we might piece together in pseudo language as
Things to say + must/needed to + recalling + love
which makes no sense of course, but that's because the ordering is off...but it should more properly translate to something like
the love that I should have (completely) told you about