If it was the 93 episode I saw, he sang:
Get Out of My Way
Biker Like an Icon
and then closed the show with Hey Jude
The best skit was the one he did with Chris Farley, "The Chris 'Farley Show".
If you remember how Chris portrayed an inept interviewer, he would always begin his questions with "Do you remember when.........????"
Well, he asks Paul, "Uhh, do you remember, do you remember when you were with the Beatles?"
Paul responds with a simple yes. Chris sez "That was awesome".
Of course, Chris brings up the "Paul is Dead" rumor from back in the 60s then asks Paul, "You weren't really dead, were you?"