How much effect does altitude have on spring gun velocity? I'm wondering if sea level velocities are higher due to higher air density than the velocity of the same rifle at 3500ft?

Hi.
I dont know the exact answer. Anywat, take into consideration that on the contrary to your point, the smaller air density results lower resistance to the pellet...
So answer is not trivial.