For me, the most intuitive explanation is that:

Force = change in momentum with time

Energy = Force x distance

Now consider how much energy can be dissipated by a tiny change in momentum over a small distance dx, when we are at a given velocity v:

dE = Fdx = (dp/dt)dx = m(dv/dt)dx = mdv(dx/dt) = mv*dv

The intuition is that in order to apply a force through some distance, I have to change the velocity of an object by dv. But, the distance I just traveled also depends on the current velocity v. That's why the total energy available isn't just simply proportional to velocity - every time we change v, the amount of force available goes down, too.

Summing all the little bits of energy dE over our velocity changes dv, from the starting velocity down to zero, and we get the formula for kinetic energy.

BTW, the intuition here really starts from the idea that force = momentum change with time. The definition of "force", "momentum", and "energy" can be maddeningly circular, even if we have clear mathematical representations and a common world we experience.