Supersonic turbulent flows of magnetized gas are believed to play an important role in the dynamics of star-forming clouds in galaxies. Understanding statistical properties of such flows is crucial for developing a theory of star formation. In this Letter we propose a unified approach for obtaining the velocity scaling in compressible and super-Alfvénic turbulence, valid for the arbitrary sonic Mach number, M(S). We demonstrate with numerical simulations that the scaling can be described with the She-Lévêque formalism, where only one parameter, interpreted as the Hausdorff dimension of the most intense dissipative structures, needs to be varied as a function of M(S). Our results thus provide a method for obtaining the velocity scaling in interstellar clouds once their Mach numbers have been inferred from observations.