I apologize in advance, but I'm going to make the problem look worse first so that I can explain it:
Imagine that instead of you measuring the velocity from the station where the rocket is launched - let's call it station A - you measure instead from station B, which is moving away from station A at some high speed. And imagine that station A launches two identical rockets, one toward you and one away from you.
Since we're operating under the well-tested current theory of special relativity, we understand that we can either say "B is moving away from A" or with equal correctness "A is moving away from B" since we can declare either one as "stationary" for purposes of measuring velocities with respect to our chosen coordinate system. So let's start over and say that Station A is moving at speed away from Station B and launches two rockets.
Of course, before they launch from A, both rockets will have a certain kinetic energy based on their motion, and that energy will be equal for the two identical rockets. When we launch them, however, that begins to change: one of them is starting to move away from us even faster, while the other begins moving away from us slower. After some time, in fact, one will be moving away from us at twice the speed it originally had - that is, four times the kinetic energy - while at the same time the other is moving away from us at zero relative velocity: no kinetic energy whatsoever! Now we're really mixed up, because both rockets did the exact same thing but one ended up with a very high kinetic energy and one with no energy whatsoever.
The issue I hope to highlight with that example is that kinetic energy is frame-dependent and not an intrinsic energy for an object. That's why you can safely ride along in a car moving at 100km/h along a road but not be safely struck by a car moving at 100km/h along a road; if you travel with the car, it has zero kinetic energy in your frame, but if you're standing on the road it has a very high kinetic energy in your frame. Kinetic energy is relative.
On another note, I said before that the two rockets are doing "the same thing," but in any given single frame of reference that's not quite true. Obviously, in my example above, from the frame of station B one rocket is losing kinetic energy and the other is gaining kinetic energy, for example. But that's only considering the rockets themselves: those are being propelled by launching photons the other direction, and those photons are expelled with a certain energy themselves. If you were to measure the energy of the photons themselves, (attaching a small mirror to the back of the rocket headed toward you so that you can see the "exhaust") you would notice that over time the exhaust of the rocket moving away from you seems less energetic and the exhaust of the rocket moving toward you seems more energetic. That is to say, photons launched toward you are less energetic than photons launched away from you... which was the same conclusion we came to with the rockets themselves launching from Station A, and again is a consequence of the relativity of kinetic energy. But this time we can more directly say that one is "red-shifted" and the other "blue-shifted."
EDIT: It may also be simpler to imagine the solution if you use a normal reaction drive with massive exhaust. The exhaust is low mass but leaves at high speed; the rocket is higher mass and thus gains less velocity from the reaction. The kinetic energy increases by the same amount in opposite directions for each body of mass (taking all the exhaust as a "body"), otherwise we're getting energy for free from somewhere. Also, since massive exhaust has subliminal expulsion speed, you can have a case where the rocket is accelerating away from you but the exhaust is also moving away from you, which isn't possible with photon drives. But in all cases, photons or not, the total energy of the system is conserved: measured from an inertial coordinate system, the rocket "gains" the same amount of energy that the exhaust "loses," and the measured exchange rate does increase quadratically.
I think you've misread the article. It says rocket engines can attain up to 70% $\eta_c$, which is only the cycle efficiency (how well it turns the energy of the fuel into mechanical energy). This is not the propulsive efficiency.
Unfortunately, for a rocket much of this mechanical energy is used to (wasted..) increase the KE of the exhaust rather than the rocket. As the article mentions, optimum efficiency is when the exhaust speed and rocket speed are matched. But this ends up being horrible for fuel consumption.
Being able to throw the mass of the earth or the atmosphere around makes regular propulsion much more efficient.
In one of your comments you linked to the question Velocity and kinetic energy, violating galilean relativity and said that the efficiency of a car drops with speed. I wouldn't agree with that statement. The question was specifically about interpreting energy in different frames.
If we stick to to just the frame where the ground is at rest (a very valid frame for travel on the earth), then the theoretical efficiency of your battery car approaches 1 as you eliminate drag. The energy of the battery can be given into KE of the vehicle almost entirely since the earth is so massive.
Best Answer
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.