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: 던
vs 았(었,였)던
.
~던 - 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