Wow! I’m impressed. I like ntm’s analysis in the comments. My only concern would be that not all of the energy goes into heating the bullet since some must be used to propel it forward. I’ll consider the 45 g bullet as a test case. Real bullets have speeds ranging anywhere from 180-1500 m/s. We can use the formula for kinetic energy to determine how much of the 18,942 J goes into linear motion. Plugging in the slowest bullet speed, we get
kinetic energy = (mass) · (velocity)2 / 2
= (45 g) · (180 m/s)2 / 2
= 730 J,
while the fastest bullet speed gives a kinetic energy of
= (45 g) · (1500 m/s)2 / 2
= 51,000 J.
In the case of the former, 730 J is barely a significant figure compared to the muzzle energy, which means that most of the energy will likely go into heating the bullet1. In the latter case, there’s not even enough energy to propel the bullet forward never mind heating it. If the muzzle energy is 18,942 J, then the absolute fastest a 45 g lead bullet can move is about 920 m/s, and that would mean all the energy goes into kinetic motion rather than heat. For a 3.97 g ice bullet, the fastest speed achievable for a bullet absorbing all that energy is 3100 m/s.
Even if all the energy is transferred directly to kinetic energy, there is still air friction that will heat the bullet. At high speeds, the frictional drag force is proportional to the velocity squared:
drag force = - (drag coefficient) · (air density) · (area of the bullet) · (velocity)2 / 2.
The air density is 1.2 kg/m3. I’ll assume the cross-sectional area of the bullet is about 0.1 cm2 (i.e. about 0.3 cm by 0.3 cm.) The drag coefficient for a bullet2 is about 0.295. Plugging these numbers in, we find the total drag force is,
drag force = - (0.295) · (1.2 kg/m3) · (0.1 cm2) · (3100 m/s)2 / 2
= -17 N.
We can compute the total work done by air friction on the bullet by multiplying this force by the distance traveled. Some guns have barrels that are as small as 10 cm, so the total work done on the bullet can be estimated by3
work = (force) · (distance)
= (-17 N) · (10 cm)
= -1.7 J.
If this is the only work that goes into heating the bullet, then its temperature change can computed as
temperature change = (energy) / [(mass) · (specific heat)]
= (1.7 J) / [(3.97 g) · (2.05 J/g·K)]
= 0.21 K.
This means the bullet could be 1 K (or equivalently 1°C) below the melting temperature and it would still fire!
What gives? Didn’t MythBusters bust this myth? It turns out our assumption that all the energy went directly into the kinetic energy of the bullet is bupkis. The truth lies somewhere between ntm’s result and my own. If all the energy goes into translational motion, then the bullet will make it out of the barrel with no problems. If all the energy goes into heating the bullet, it will melt almost instantaneously. As ntm very accurately points out, you can only lower the temperature of the bullet to absolute zero, so there’s only so much we can freeze it. Whether or not an ice bullet will ever work depends on how efficient your rifle is. If we cool the bullet to zero temperature, it will be able to absorb 2200 J before it melts4. Whether or not the bullet melts depends on how efficient the rifle is at transferring energy to the bullet. So long as less than 12% of the muzzle energy is converted to heat, the bullet should make it out of the barrel fine.
At any rate, very good work, ntm. I am suitably impressed.
 There is also some energy in the recoil of the rifle. This should have much less kinetic energy than the bullet. You can see this if you solve for the conservation of both energy and momentum.
 Since they’re made of different materials, it’s unclear whether or not ice bullets and lead bullets will had the same drag coefficient, but this is a reasonable order of magnitude estimate.
 Because of friction, the bullet will slow down so technically we can’t assume the velocity is constant over all 10 cm. Because of this, our estimate here should be considered an upper bound for the work done on the bullet. We can also include the latent heat necessary to undergo a phase change, but this will be small.