I agree that this feels intuitive, that potential energy should increase linearly with height.

But in the end, it's all up to the units/quantities we choose to measure, no? If we, say, decided to measure "Squenergy" in Sqoules, with 1Sq² = 1J, then suddenly, squenergy does increase linearly with speed! The formula for kinetic Squenergy becomes sqrt(m/2)v.

Of course this complicates other stuff, like potential Squenergy becoming sqrt(MgH), it not being additive, etc.