4998 = 2 × 3 × 72 × 17
“I am leaving, I am leaving”
[I read “The Nine Billion Names of God” when I was about 11-12, and the ending freaked me out.]
4999, prime.
But the fighter still remains
[I just read for the first time and found it funny. Predictable, of course, but so very well written! I enjoyed it, so thanks @Bonum_Legatum!]
5000 = 23 × 54
He still remains.
[ 
YAY, we’re 0.5% of the way to a million! 
]
5001 = 3 x 1667
Lie la lie, lie la lie la lie la lie, la la lie la lie 
[celebrating]
5002
Lie la lie, lie la lie la lie la lie, la la lie la lie
5003 = a prime, or 5.003 × 103
Lie la lie, lie la lie la lie la lie
5004
Lie la lie, lie la lie la lie la lie, la la lie la lie
5005 = 5 × 7 × 11 × 13
Lie la lie, lie la lie la lie la lie
5006
Lie la lie, lie la lie la lie la lie, la la lie la lie.
[Let’s skip the “thank you and goodnight,” and move on to another song. Suggestions, anybody?]
5007 = 3 × 1669
Johnny’s in the basement
[I don’t think we’ve done this one before.]
5008
Mixing up the medicine
[I don’t recall that we have. Good choice.]
5009, hitting a lot of primes recently 
I’m on the pavement
5010
Thinking about the government
5011, another prime, or 5.011 × 103
The man in a trench coat
5012
Badge out, laid off
5013 = 32 × 557
Says he’s got a bad cough
5014 = 2 x 23 x 109
wants to get it paid off
5015
Look out kid
5016 = 23 × 3 × 11 × 19
It’s somethin’ you did
5017
God knows when