The first I ever heard of Cheap Trick was in about 1975 when I heard them open for KISS.
The Worzels - Wurple Diddle I Do
The Frim Fram Sauce:
“I want the frim fram sauce,
with the ossinfay,
with shifafa on the side.”
When It’s Night-Time in Italy It’s Wednesday Over Here:
Come to think of it, for more nonsense in the style of “I Am the Walrus,” there’s The Rutles’ “Piggy In the Middle.”
And I’m sure that this song (“Traps, Ensnares” by Daniel Amos) was deliberately written in an “I Am the Walrus” vein:
So was this (“Everybody Else Is Wrong” by Utopia), though it’s not as good an example of nonsense:
I’m amazed how many of the phrases are inteligible backwards!
When I saw them in concert, Robin threw a KISS album into the crowd. I could not tell if the crowd threw it back.
I was just as amazed by that as how many were completely incoherent backwards. I have to wonder if Weird Al has seen that version, and what he makes of it.
It also says something that Weird Al made a video that’s so entertaining in both direction, forwards and backwards
On the Amazon, the prophylactics prowl On the Amazon, the hypodermics howl On
The Amazon, you’ll hear a scarab scowl and sting zodiacs on the wingAll the stalactites and vicious vertebrae
Hunt the stalagmites while laryngitis slay
All that parasites that come from Paraguay in the spring
Hmm, hmm hmmm
Most people know Yakety Sax as the “Benny Hill music”, but it was really used mostly in the end chase skit. The music he played was most often was a four song medley of Doo-Bee-Doo-Bee-Doo by Giorgio Moroder , Für Elise by Ludwig van Beethoven, Mah-Nà, Mah-Nà by Piero Umiliani and Gimme Dat Ding. The one on the show was done by his house band, which I can’t find. Here’s the originals. I have a big affection for them.
Almost everything by They Might Be Giants. Their songs are instant earworms for me.
A favorite kind of “nonsense” song is where the lyrics comprise words and phrases strung together for no apparent reason other than they made the songwriters feel good.
In this category are “Poppin’ Circumstance” (NRBQ) and the Fountains of Wayne’s “Someone’s Gonna Break Your Heart”:
We don’t promise and we tell no lies
Learn to paddle when the waters rise
Melancholy comes
Like a robin at your window
Whistle in the sweet pine trees
The imaginary airport breeze
It flickers and flows
Fans fires in the road and
All we want to do is go home
Someone’s gonna break your heart
One cold gray morning
They sing cute songs, but.I think the main reason I like Istanbul (Not Constantinople) and Particle Man is because they were on Tiny Toons.
And I’m amazed how much more ‘Dylan-esque’ the backwards version sounds. 
“Be kind to your web-footed friends…”
Seconded, both the incomprehensibility and the favourite band parts.
Another band on the same label : Dead Can Dance.
Sometimes the lyrics are in obscure-to-me languages like 16th C. Catalan
Sometimes they’re just glossolalia , like the first part of Rakim:
or Saldek:
John Lennon loved this song.
REM got mentioned upthread but nothing for “It’s the End of the World As We Know It”??
Leonard Bernstein!!
I’m fascinated by glossolalia. When I was in my early teens I was a Pentecostal Christian and this was very common. I did it all the time. A lot of people think it’s faked, but it’s not that simple. It’s an altered state of consciousness. It’s not the “holy spirit” but it is this weird thing people can learn to do to themselves. And when I did it I didn’t feel like I had control of my body.