An instability near the transition to collective motion of self-propelled particles is studied numerically by Enskog-like kinetic theory. While hydrodynamics breaks down, the kinetic approach leads to steep solitonlike waves. These supersonic waves show hysteresis and lead to an abrupt jump of the global order parameter if the noise level is changed. Thus they provide a mean-field mechanism to change the second-order character of the phase transition to first order. The shape of the wave is shown to follow a scaling law and to quantitatively agree with agent-based simulations.