Some of the ones mentioned are true non-sequiturs.
Some of them, though, DO relate, if you stop and think about them. Those titles are often descriptive; for example, if I go to a tavern called "The Cavern Bar" and write a song about people and events that I find there, then "The Cavern Bar" is a reasonable name for the song, even though it isn't named directly in the lyrics. The connection doesn't have to be "an equal sign", nor do the lyrics have to contain the title.
For example, "Sympathy for the Devil" is all about the devil; "Please allow me to introduce myself..." is the devil himself singing. The devil was the one who "made damned sure that Pilate washed his hands to seal his fate", etc... The song is --for its day-- rather sympathetic in tone towards the devil, and might be seen as a plea for sympathy for the devil, being made by the devil. It isn't such an obscure or non-sequitur title, IMO.
I suspect that many others had meaning for the authors. Perhaps "The 59th Street Bridge Song" was written on or near that bridge, or was inspired by a person or event witnessed at or near that bridge. It's a sad song about a guy down on his luck, so perhaps it was about someone who wanted to jump off the bridge to commit suicide? This is all speculation; we cannot know, but there are possible, plausible links. On the surface, it seems non-sequitur, though. I assume that most such titles have a relevance, even if it isn't known to us.
Then there are the truly bizarre and non-sequitur titles. Maybe these are given just to make us curious, to make the "artists" seem more artsy, or maybe they just didn't think of a good title, and randomly slapped on the first thing that popped into their heads. Who knows? Those titles truly belong on this list.
I've run across some that struck me at the time, but the few I could think of have already been listed in this thread. I suppose going through my music collection would come up with more, but I'm too lazy to do that, and can't think of any others.