Well, there are roughly 500 servers. Sha spawns roughly 5 minutes after a kill. Assumed he's killed within 20 minutes of his spawn, this leaves a server at approximately. 3 kills an hour. This translates to 72 kills a day. But lets go ahead and assume that during the dead hours of the day, he is not killed. Lets just say between 3 and 9 am.
This brings a hypothetical kill to 54 kills a day. Seems reasonable.
54 x 500 servers = 27,000 kills a day.
October 9th was his hotfix to spawn more frequently. There have been 121 days since then.
This brings the hypothetical number to 3,267,000 kills since October 9th.
Obviously not all servers kill Sha as frequently as others. Some will kill him more than 3 times per hour, some will kill him less. Even if you cut the kill total in half to 3 kills every 2 hours, you're still looking at 1.6 million kills.
So, yes. Millions.
I'll go a step further! Because I like big numbers.
assuming a full 40 man group kills him each time, you're looking at 130,680,000 individual characters that have killed Sha of Anger, had a chance at loot, and not received it.
Edit: and before anyone even replies with "NO ONE KILLS SHA THAT MUCH" , Yes, they do. Some servers have 40 mans in queue waiting for a respawn. Some servers Sha is sitting upright for hours.
To reach 1 million kills in 121 days, you would need to average 16 Sha kills per server across all 500 servers.
Some can be at 32, some could be at 8.
16 per realm, per day, is the magic number.