The answer to this question has significant overlap with my answer on piano tuningpiano tuning. There, I discuss how a thick wire has an extra restoring force, in addition to its tension, from its resistance to bending. This modifies the usual wave equation to $$v^2 \frac{\partial^2 y}{\partial x^2} - A \frac{\partial^4 y}{\partial x^4} = \frac{\partial^2 y}{\partial t^2}.$$ This case is the other way around: the tension is negligible, so we only have the 'extra' term. The wave equation becomes $$-A \frac{\partial^4 y}{\partial x^4} = \frac{\partial^2 y}{\partial t^2}.$$ Plugging in an ansatz of $\cos(kx-\omega t)$ gives the dispersion relation $$Ak^4 = \omega^2.$$ That is, $\omega \propto k^2$. Since $k$ is inversely proportional to length, $$\omega \propto 1/L^2$$ as desired. A bar $\sqrt{2}$ times shorter makes a tone twice as high.
As you saw, the wave speed must change for the results to make sense. The phase velocity of a wave is $v_p = \omega / k$, and this is constant only for the simplest dispersion relation, the ideal wave equation $\omega = vk$. In this case, we have $\omega \propto k^2$, which implies $v_p \propto k$. Waves with shorter wavelength, like the ones on the smaller bars, travel faster.
But this doesn't mean anything about the smaller bars is different. The phase velocity changes because wave propagation is fundamentally different on bars than strings; it exhibits dispersion.