The atmospheric neutrino data collected by the Super-Kamiokande experiment span about four decades in neutrino energy E, and are thus appropriate to probe the energy dependence of the oscillation wavelength \lambda associated to nu_mu<--->nu_tau flavor transitions, when these are assumed to explain the data. Such dependence takes the form \lambda^{-1}\propto E^n in a wide class of theoretical models, including ``standard'' oscillations due to neutrino mass and mixing (n=-1), energy-independent oscillations (n=0), and violations of the equivalence principle or of Lorentz invariance (n=1). We study first how the theoretical zenith distributions of sub-GeV, multi-GeV, and upward-going muon events change for different integer values of n. Then we perform a detailed analysis of the Super-Kamiokande data by treating the energy exponent n as a free parameter, with unconstrained scale factors for both the amplitude and the phase of nu_mu<--->nu_tau oscillations. We find a best-fit range n=-0.9 \pm 0.4 at 90% C.L., which confirms the standard scenario (n=-1) as the dominant oscillation mechanism, and strongly constrains possible concurrent exotic processes (n \neq -1). In particular, we work out the interesting case of leading standard oscillations plus subleading terms induced by violations of special or general relativity principles, and obtain extremely stringent upper bounds on the amplitude of such violations in the (nu_mu,nu_tau) sector.