We measure experimentally the penetration depth d of spherical particles into a water-saturated granular medium made of much smaller sand-sized grains. We vary the density, size R, and velocity U of the impacting spheres, and the size delta of the grains in the granular medium. We consider velocities between 7 and 107 m/s, a range not previously addressed, but relevant for impacts produced by volcanic eruptions. We find that d proportional to R-1/3 delta U-1/3(2/3). The scaling with velocity is similar to that identified in previous, low-velocity collisions, but it also depends on the size of the grains in the granular medium. We develop a model, consistent with the observed scaling, in which the energy dissipation is dominated by the work required to rearrange grains along a network of force chains in the granular medium.