Two analogies, to get a closer feeling of the situation for both the bullet in the sand and in water. Let's scale things up and let's not care too much about scale dependency or scale independency, which is another issue.
Imagine we fire a huge bullet into a huge pile of rocks. Say the spatial dimensions of the rocks and bullets are $100$ times as big as the spatial dimensions of the sand grains and the "normal" bullet. What will happen? It's not so difficult to see that the rocks will get damaged when they absorb the kinetic energy of the bullet. So the kinetic energy of the bullet is used to damage the rocks. There is a "damaged rock zone" (sounds like a music program) developing around the top of the bullet. Of course, the rocks in contact with the passing bullet will also heat up due to friction, but this is a minor part of the total absorbed energy. The rocks experience no change in total kinetic energy.
Now imagine firing the same bullet, with the same speed at a volume of tiny unbreakable spheres which have a specific mass that's comparable with that of the rocks. When they move wrt each other they experience very little friction (say they are lubricated). What will happen? The spheres will, just as the rocks, absorb the kinetic energy of the bullet. The bullet pushes the spheres sidewards and the spheres will get kinetic energy which will eventually be gone due to the small friction. Nothing is damaged.
I don't think it's hard to see that the bullet can go a longer distance through the tiny spheres than through (the water) than through the rocks (the sand) before coming to a full stop. You can say this begs the question but these analogies are only meant to get a feeling for the situations. The ultimate reason must be that that damaging and breaking rocks is a more efficient process for absorbing kinetic energy than pushing aside tiny spheres.
Note that the tiny spheres are not in motion before the bullet hits them. I don't think that the motion of the water molecules is of much importance for the absorption of the bullet's kinetic energy (that is if it didn't freeze).
Note also that if the bullet has a flat front side then it's the question if it will penetrate the water (in this case the bullet has to be fired at the water at a right angle). In the analogy, it remains to be seen if a huge bullet with a flat front side will penetrate.
If one refines the analogies a bit, especially the tiny spheres one, (say by letting the tiny spheres have a mutual attraction, providing them with a kind of surface tension), one is able what happens for example at the back of the penetrating bullet.