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 δ 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∝R^{1/3}δ^{1/3}U^{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.