The “as song went” seems to match the tense of the whole sentence
Sentences don't have a tense, clauses do. Consider the sentence:
I renewed my passport yesterday, because I will be travelling next month.
Not only is it clearly in both the past and future tense, but it clearly has to be to convey its meaning, yet also the connection between the past-tense clause and the future-tense clause is clear.
Now, there are rules about how the tenses of different clauses should match in certain cases, but this needs to consider the relationship between those clauses.
In the case of your example, we can start by considering the first and last:
When I was a small boy I fell in love with a little girl.
Here the two parts do need to match tense*, because the first identifies the point in time as in the past, and the second as something that happened then.
Now, consider the third:
..., when I was shorter than a Christmas tree,...
This also has to match, because it is also identifying the point in time, repeating the first in a different way.
However, the second:
..., or as a famous song [goes/went],...
Does not have to match, because it is not referring to that point in time, or to action that took place then.
The song that went "when I was shorter than a Christmas tree", presumably still does. It's therefore technically correct to use either tense.
This parenthetical thought probably does belong to the time of the action, but the time of the reporting. That is to say, you didn't at the time think about the fact that you were so small, but are thinking it now. This would lean us towards the present tense form:
..., or as a famous song goes,...
Generally, it would be strange to talk about how a song went without a particular reason. We might if the song was once often sung, but now is not. We might if the words had changed:
The song "Happy Birthday" originally went "Good morning to you!/Good morning to you!"
We might if we the song was more directly relevant to the point in time:
It was only a week until Christmas, so we "decked the halls", as the song we were singing went.
We might if we focused on the song as an event.
There was a song that went...
But note:
He wrote a song that goes/went...
In the second the writing of the song is the event, not the song, so we're back to both being acceptable.
We might talk about how a song or poem went if it was lost, though that prevents us from knowing how it went to speak of it, though we can just about say:
Sappho's "The Ode to Anactoria", or "To a Woman" went, "...For when I see thee but a little, I have no utterance left, my tongue is broken down, and straightway a subtle fire has run under my skin, with my eyes I have no sight, my ears ring, sweat pours down, and a trembling seizes all my body; I am paler than grass, and seem in my madness little better than one dead. But I must dare all, since one so poor..." but alas we don't know how it continued.
But here, one might still use the present tense, after all we know how that bit goes.†
In all, you could use either. It would generally be more usual in this sort of case to use the present tense for what is a present-tense comment on a song that still goes that way, but you might use the past if you had a particular reason to tie the song's lyrics to the time you are talking about.
*Or at least they need to match in the time of the tense, there are other cases where we might use different types of past-tense for events around the same time, and so on.
†Or at least in this example, how H. T. Wharton's goes, we have the original, and mny other translations, but Wharton's is my favourite.