The answer to this question has significant overlap with my answer on piano 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: now 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}.$$ If you try to solve this equation with waves like $\cos(kx-\omega t)$, you find the dispersion relation $$Ak^4 = \omega^2.$$ That is, $\omega \propto k^2$. Since $k$ is inversely proportional to length, this means that $$\omega \propto 1/L^2$$ as desired. A bar $\sqrt{2}$ times shorter makes a tone twice as high.
As you noticed, 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 \propto k$. In this case, we have $\omega \propto k^2$, which implies $v_p \propto k$. The waves on the smaller bars are indeed traveling faster.
But this doesn't mean anything about the smaller bar is different. The phase velocity $v_p$ changes because wave propagation is fundamentally different on bars than strings; it exhibits dispersion.