Where does the extra kinetic energy of the rocket come from?
You've noted that at high velocities, a tiny change in velocity can cause a huge change in kinetic energy. And that means that the thrust due to burning fuel seems to be able to contribute an arbitrarily high amount of energy, possibly exceeding the chemical energy of the fuel itself.
The resolution is that all of this logic applies to the fuel too! When the fuel is exhausted, it loses much of its speed, so the kinetic energy of the fuel decreases a lot. The extra kinetic energy of the rocket comes from this extra contribution, which can be arbitrarily large.
Of course, the kinetic energy of the fuel didn't come from nowhere. If you don't use gravity wells, that energy came from the fuel you burned previously, which was used to speed up both the rocket and all the fuel inside it. So everything works out -- you don't get anything for free.
For those that want more detail, this is called the Oberth effect, and we can do a quick calculation to confirm it. Suppose the fuel is ejected from the rocket with relative velocity $u$, a mass $m$ of fuel is ejected, and the rest of the rocket has mass $M$. By conservation of momentum, the velocity of the rocket will increase by $(m/M) u$.
Now suppose the rocket initially has velocity $v$. The change in kinetic energy of the fuel is $$\Delta K_{\text{fuel}} = \frac12 m (v-u)^2 - \frac12 mv^2 = \frac12 mu^2 - muv.$$ The change in kinetic energy of the rocket is $$\Delta K_{\text{rocket}} = \frac12 M \left(v + \frac{m}{M} u \right)^2 - \frac12 M v^2 = \frac12 \frac{m^2}{M} u^2 + muv.$$ The sum of these two must be the total chemical energy released, which shouldn't depend on $v$. And indeed, the extra $muv$ term in $\Delta K_{\text{rocket}}$ is exactly canceled by the $-muv$ term in $\Delta K_{\text{fuel}}$.
Sometimes this problem is posed with a car instead of a rocket. To understand this case, note that cars only move forward because of friction forces with the ground; all that a car engine does is rotate the wheels to produce this friction force. In other words, while rockets go forward by pushing rocket fuel backwards, cars go forward by pushing the Earth backwards.
In a frame where the Earth is initially stationary, the energy associated with giving the Earth a tiny speed is negligible, because the Earth is heavy and energy is quadratic in speed. Once you switch to a frame where the Earth is moving, slowing the Earth down by the same amount harvests a huge amount of energy, again because energy is quadratic in speed. That's where the extra energy of the car comes from. More precisely, the same calculation as above goes through, but we need to replace the word "fuel" with "Earth".
The takeaway is that kinetic energy differs between frames, changes in kinetic energy differ between frames, and even the direction of energy transfer differs between frames. It all still works out, but you must be careful to include all contributions to the energy.
Another much clearer way to see the effect of the Oberth effect is when you add the Potential energy to the equation.
When you perform a rocket burn inside the gravity well of a massive body, the propellant ends up in a lower orbit than if you perform the rocket burn outside of the gravitational well.
The difference in the Potential Energy of the propellant will equal the difference in the Kinetic Energy of your space probe.