Kinetic energy "paradox" -- where am I wrong here? Body $A$ is at rest and has mass $2$, so the energy required in order to accelerate it to a speed of $v$ is $v^2$, and so the energy required in order to accelerate it to a speed of $2$ is $4$.
On the other hand consider that we first accelerate $A$ to speed $1$, requiring an energy of $1$, and assume that a body $B$ that was already moving at speed $1$ is positioned such that after $A$ reaches speed $1$ both bodies are right next to each other. From $B$'s point of view $A$ is now at rest and so to bring $A$ to speed $1$ in this reference frame an energy of $1$ is needed. Looking at it from the original reference frame we see that $A$ got up to speed $2$ while requiring only $2$ units of energy rather than the expected $4$.
I'm guessing the solution to this "paradox" ought to somehow depend on the fact that $KE$ is obviously dependent on reference frame, but from a practical point of view I just can't see what's wrong with saying that if I have have two batteries each capable of delivering an energy of $1$ then I can use the set-up above to get a stand-still object to accelerate to speed $2$ using only these two batteries, while the math says $4$ are going to be needed.
(For instance I can deliver the second battery to the moving object as it passes by me; alternatively I can speed up the second object myself in tandem with the first, and there is no reason to assume that the second object needs to have any specific minimal mass for this experiment, so I can assume it has mass close to $0$ so that it takes little to no energy to accelerate it.)
Where's my mistake?
 A: Long story short: work and change in kinetic energy are frame-dependent quantities, although the work-energy theorem holds in both frames. Using the fact that mass and force are frame-independent quantities, we can see that the extra change in kinetic energy as seen in the non-moving frame is due to the fact that an observer in this frame observes the force exerted as acting through a larger distance than that observed in the moving frame.  In order to resolve the mystery of "where is the extra energy", we note that the total change in energy observed in the non-moving frame has two components, and the "missing" energy comes from the work that the one of the object needs to do in order to maintain a constant speed.
Here are the details:

Let's consider the following situation.  A physics student is standing on a cart moving at a constant speed $v$. Let's call this reference frame $A$. She throws a ball forward, exerting a force $F$ over some distance, and the final speed of the ball ends up being $v_{\textrm{A}}$ in this moving frame.  Her lab partner is standing stationary on the ground (frame B) observing this process, and he sees the final speed of the ball to be $v_{\textrm{B}}=v+v_{\textrm{A}}$.  Ignoring the factors of mass (because mass is a Galilean invariant), the change in kinetic energy observed in frame A is
$$
\Delta K_{\textrm{A}}=\frac{1}{2}v_{\textrm{A}}^2,
$$
and the change in kinetic energy observed in frame B is
$$
\Delta K_{\textrm{B}}=\frac{1}{2}(v+v_{\textrm{A}})^2-\frac{1}{2}v^2 = \frac{1}{2}v_{\textrm{A}}^2 + vv_{\textrm{A}}>\frac{1}{2}v_{\textrm{A}}^2 = \Delta K_{\textrm{A}}.
$$
Apparently, there is a larger change in kinetic energy in frame B as in frame A, as the OP observed!
To resolve this mystery, we need two things.  First, it can be straight-forwardly proven that the force $F$ exerted on the ball is also a Galilean invariant, and so both observers see the same force exerted on the ball.  However, since the first student is standing on the cart, she sees herself exerting a force on the ball through some distance $d$, and so the work done on the ball is
$$
W_{\textrm{A}} = Fd.
$$
In frame B, the distance through which the force is exerted includes the distance that the cart has traveled during this time, i.e.,
$$
W_{\textrm{B}} = F(d +v\Delta t),
$$
assuming that that the throw takes an amount of time $\Delta t$.
The work energy theorem holds in both of these frames, and we can see how the energy added to the ball as observed in frame B is larger than that observed in frame A!  In fact, we can show that they are equal.
The amount of time taken to accelerate the ball from a speed of $0$ to a speed $v_{\textrm{A}}$ over a distance $d$ in frame A is given by (again, ignoring mass)
$$
\Delta t = \frac{\Delta v_{\textrm{A}}}{a} = \frac{v_{\textrm{A}}}{F},
$$
and so, plugging this into the expression for the work done in frame B, we get
$$
W_{\textrm{B}} = F(d +v\Delta t)= F\left(d +v\frac{v_{\textrm{A}}}{F}\right) = Fd + vv_{\textrm{A}}.
$$
We can see that the extra work done as observed in frame B is exactly the extra amount of energy gained as observed in frame A compared to frame B.

Now, there's still some intuitive stuff to work out.  Sure, work and changes in kinetic energy are frame-dependent, but it still feels like the energy is lost in going from one frame to another.  Where is the meaning of the extra energy as observed in one frame versus the other.  In particular, the OP mentions energy used by batteries.
In frame A, imagine that a battery-powered machine is the one throwing the ball.  It really only has to supply an energy equal to $v_{\textrm{A}}^2/2$ to accelerate the ball in the moving frame!  So where is that extra energy as seen in frame B coming from? It's coming from the cart.  The cart is given a backwards kick by the pitching machine, because the machine is pushing backward on the cart in order to push forward on the ball.  Thus, the cart must be powered in order to remain at a constant speed during the throw.  How much energy is require to remain at a constant speed?
For the sake of argument, let's pretend that the pitching machine has zero mass.  Then the force exerted backward on the cart is equal to the force exerted forward on the ball, by Newton's 3rd Law. To remain at constant speed during the throw, the cart must counteract this force by exerting its own force backwards on the ground.  Of course, the amount of work done during this process is $Fv\Delta t$, and we already showed that this is equal to the extra amount of energy that is missing.
A: 
Where's my mistake?

Your mistake is in neglecting momentum. In order to change speed you need momentum as well as energy. So, in order to accelerate, your object $A$ must interact with some other object.
Regardless of the mechanism you use, whatever energy seems to be missing, if you examine the other object, the one that $A$ is interacting with, there you will find the missing energy.
A: In the second moving reference frame, that battery dumps 1 unit of energy via force over a distance. From the perspective of the original at rest system, the battery is already moving and hence force is applied over a larger distance, accounting for the energy discrepancy.
Likewise, imagine the 2nd battery remains at rest in the 2nd frame. It applies a force, for which there is an equal an opposite force for the duration of acceleration. No work is done holding the battery in place because it's not moving.
But in the original frame it is moving, so that static force keeping the battery locked down is now seen as a dynamic force, and extra $W=\int Fdx$ is added to the final kinetic energy.
