I also had this problem. It seems unintuitive that somehow going from 50 to 60 mph adds a different amount of oomph to an object than going from 60 to 70 mph.

I'm going to base my answer on this physics stackexchange answer. I'll rephrase it to make the mathematical steps more clear, but I recommend reading that answer as well if you know high school algebra well.

Hopefully you have the intuition that energy is some property that objects have which can cause internal transformations in matter. Whenever an object collides and as a result deforms or heats up, that's kinetic energy acting on the object.

So let's look at a situation that makes it easy to account for all the kinetic energy - a clay ball hits a wall. It will splatter, and the size of this deformation can be used to calculate the energy. If two clay balls of equal size hit a wall and splatter to the same extent, they had the same amount of energy. Let's say the balls were moving with speed v, and had an amount of energy E.

Our first step is to change this experiment. Instead of throwing the balls at the wall, we throw them at each other. They splatter in the air instead of on the wall, coming to a complete stop. They were both still moving with speed v, but in opposite directions. When we do this experiment, we find that the amount of deformation each ball undergoes in this collision is the same as when they hit a wall. This makes sense - each ball has energy E, so the entire collision has energy 2E, but it's spread out through twice as much mass. Each ball undergoes an E's worth of explosion, the same as if they each hit a wall.

Our second step is to change this experiment once again. Throw the balls a each other, but now observe them from a car moving forward at speed v. The ball we're following looks like it's hanging in the air, while the other ball is moving toward it at speed 2v. Now to see what happens when they collide, you'll need to keep track carefully. To a person standing on the ground, the two balls stopped moving completely, and fell straight down. But since we're in a car moving forward at speed v, the collided balls are now moving backward at speed v. From the car, it looks like the 2v ball came in, collided, and knocked the combined system backwards.

Now the crucial step - other than this change in relative speeds, the collision looks identical. Us being in the car doesn't change the events. The splatter of each ball is the same size. So the moving ball went from 2v to v, and yet it delivered 2E's worth of energy. Going from 0 to v grants an object E worth of energy, and yet going from v to 2v grants at least 2E (in reality more, since the two-ball system is still moving, so it didn't lose all its kinetic energy to the splatter). We got here not by assuming any kind of mechanics, but by assuming that the laws of physics work the same when we're moving as when we're stationary - if we do all our math from a moving car, we should still observe the same things happening, even if we observe them happening at different speeds.

To get the exact quadratic relationship, we have to account for the fact that the two balls are now moving backwards with velocity v, which means there is an extra 2E's worth of energy stored in their motions. That's a total of 4E. If velocity v has energy E, while velocity 2v has energy 4E, that means doubling the velocity quadruples the energy, which is only possible if E(v) ~ v^(2). Then E(2v) ~ (2v)^2 ~ 4 v^2.

This argument suggests that this relationship does not come from the inherent properties of objects, the way electromagnetic energy does. That energy is somehow stored in the bonds between nuclei and electrons. Kinetic energy is some kind of property of the geometry of space and time, so just thinking about the symmetries of motion can tell us what the relationship between motion and energy must be.