Apparent kinetic energy paradox Imagine two cars (A and B) of mass $m$ that want to destroy themselves by colliding. They need a velocity of magnitude $2v$ with respect to each other to achieve the destruction that they want and they have a fixed amount of gasoline that they can share and use that will provide up to $4E$ (where $E=\frac{mv^2}{2}$) of useful energy. Now, consider the following two cases:
Case I
Car A gets to use all the gasoline. It accelerates up to a velocity of $2v$, consuming all the available energy but achieving the desired collision.
Case II
Car A and B share half of the gasoline and store the other half (each one gets to use up to $E$ of energy), and each accelerate to a velocity of $v$. The collision also happens as desired (each one was at a velocity of $2v$ with respect to one another) and, not only that, they saved $2E$ worth of gasoline.
My question is: how can it be possible for the same event to happen using only half the energy? Or, more specifically, if the event happened in the exact same way in the car's frame, what explains the difference in kinetic energy?
 A: 
how can it be possible for the same event to happen using only half the energy?

Your math is correct about the energy, but your assumption that the whole kinetic energy is converted to damage (material deformation) is wrong. After the collision the two cars might keep on going, which means only portion of (initial) kinetic energy is lost to damage.
Collisions are best understood via momentum. During a collision there is collision force between the two objects. Since the collision force is (usually) much larger than other external forces, and since it obeys third Newton's law of motion (action-reaction), the momentum before and after the collision is conserved
$$m_a \vec{v}_a + m_b \vec{v}_b = m_a \vec{v}_a' + m_b \vec{v}_b'$$
where $v$ and $v'$ are velocities just before and after the collision, respectively.
In general, there are two types of collisions: (i) elastic, in which no energy is lost, i.e. kinetic energy of the system before and after the collision is the same; (ii) inelastic, in which part of the energy is lost to heat, material deformation etc. A special case of inelastic collision is when the two particles merge together, so they become one body and have the same velocity after the collision - this is called perfect inelastic collision.
Case I
With $m_a = m_b \equiv m$, $\vec{v}_a = 2v$, and $\vec{v}_b = 0$ we have
$$2 v = \vec{v}_a' + \vec{v}_b'$$
From this it is obvious that there is some kinetic energy left in the system, i.e. not all energy is lost to collision (or damage as you call it). In case collision is perfectly inelastic, the final velocities are the same $\vec{v}_a' = \vec{v}_b' = v$ and kinetic energy before and after collision is
$$K_1 = 4 \frac{1}{2} m v^2 \qquad \text{and} \qquad K_2 = 2 \frac{1}{2} m v^2 = \frac{1}{2} K_1$$
The kinetic energy difference $\Delta K = -\frac{1}{2} K_1 = -m v^2$ goes to material deformation, heat etc.
Case II
With $m_a = m_b \equiv m$, $\vec{v}_a = v$, and $\vec{v}_b = -v$ we have
$$0 = \vec{v}_a' + \vec{v}_b'$$
Let's again assume the collision is perfectly inelastic. The final velocities are then $\vec{v}_a' = \vec{v}_b' = 0$ and the kinetic energy difference is $\Delta K = -m v^2$, just as in the Case I.
A: For the first case, from the inertial frame of the street, (that is the same of the car at rest before collision), the other car increases its kinetic energy $\Delta E_k = 2mv^2$, and the corresponding work comes from 4E of fuel. After the crash, supposing it is loose in the ground, it is accelerated to a velocity $v$ due to momentum conservation. So, the final kinetic energy is $mv^2$, and both are also plastic deformated.
For the second case, it is not possible to choose one of the cars as an inertial frame, because both accelerate. Using the street frame, they use 2E of fuel to get enough work to have a combined $\Delta E_k = mv^2$, and all is consumed in plastic deformation, because the final kinetic energy is zero.
So the energy is balanced for both cases.
If the car at rest is fixed to a wall for example in the first case, and the final velocity is zero, the surplus of energy is wasted in vibrations (or damage) on the wall.
A: You ask 'how can it be possible for the same event to happen using only half the energy?' The answer is that you have described two different events.
In one scenario you describe, two cars move in opposite directions with equal speed relative to the ground- in the other, one car moves with twice that speed relative to the ground while the second remains stationary. They are two quite different 'events'.
If you consider the case in which the cars are both moving relative to the ground, their combined momentum is zero. So when they crash, the centre of gravity of the wreckage will be stationary. In the other case, the combined momentum is 2mv before and after the crash, so the wreckage will continue to move immediately after the crash in the direction of motion of the car that was driven at 2v.
Another key point to bear in mind is that KE is frame dependent. You might like to think about how the crash would appear in the frame of reference of a helicopter flying past at 10v, say.
A: 
My question is: how can it be possible for the same event to happen using only half the energy?

Well, you are neglecting momentum, so you are also neglecting half of the energy in the first scenario.
Let's assume that the collision is perfectly plastic. With $E=\frac{1}{2}mv^2$ and $p=mv$, then in case I car A initially starts with $4E$ and $2p$ while car B initially starts with $0E$ and $0p$. After the collision, since momentum is conserved the car A+B wreckage still has momentum $2p$, so the velocity of the wreckage is $v$ and therefore the kinetic energy of the wreckage is $2E$ meaning that the amount of energy lost in plastic deformation was $2E$.
In case II car A initially starts with $E$ and $p$ while car B starts with $E$ and $-p$. After the collision, since momentum is conserved the car A+B wreckage has no momentum, so the velocity of the wreckage is $0$ and therefore the kinetic energy of the wreckage is $0$ meaning that the amount of energy lost in plastic deformation was again $2E$.
So case I wasted half of the gasoline in increasing the final KE of the wreckage. In contrast, case II didn't waste any gasoline in KE of the wreckage, which is why it was able to use less fuel.
Whenever you see a situation like this, where energy seems to not be conserved, always check your momentum too. Very often (not always but often), you will find that following the momentum will help you find the missing energy.
A: I wanted to add a slightly different perspective to the other (correct and good) answers.
Kinetic energy is not invariant under a change of frame. Imagine a box of mass $m$ at rest. If I boost into a frame moving at velocity $V$, the kinetic energy of the box is now $\frac{1}{2} m V^2$ in this new frame, even though the box never underwent any acceleration. However, changes in the total kinetic energy are the same in different inertial frames (since the change in kinetic energy is due to the work done, and work is invariant under boosts, in Newtonian physics). That implies, in any fixed frame, the kinetic energy of the box is constant, assuming no work is done on it (which, hopefully, is what you would expect intuitively -- you don't get useful energy for free).
Applying this to your situation, we see that the change in kinetic energy from the pre-collision to post-collision state is always $2E$, regardless of whether you are in the "case I" reference frame or the "case II" reference frame, as shown explicitly by Dale. However, the actual value of the kinetic energy in the post-collision state is different ($2E$ in the case I frame, $0$ in the case II frame). This is simply because there is a boost relating the two frames. So long as we only care about analyzing the collision, we can use any frame, and there are no contradictions with general principles.
Your problem, however, adds an additional element: you specify that the cars started at rest with respect to each other, and then one or both of the cars accelerated from this initial frame. The initial frame in which the cars are both simultaneously at rest picks out a special frame in which to analyze this problem. In case I, more total energy is expended to accelerate car A from the special rest frame to its pre-collision state, than energy expended to accelerate cars A and B to their pre-collision states in case II. This difference is reflected in the post-collision states (as pointed about by the other answerers): in case I the wreck has additional kinetic energy (relative to the initial special rest frame), compared to the post-collision state of case II.
You could, if you wanted, analyze the whole process in a different frame. In this scenario, in case I you would start with both cars moving at a velocity $V$, then car A would accelerate toward car $B$, then they would both collide, and end with some velocity different from $V$ -- at the end of the whole process, some energy was used to change the total kinetic energy (and therefore didn't go into the collision). In case II you would again start with both cars moving at a velocity $V$, but now both cars would accelerate toward each other, and finish moving at the same velocity $V$ after the collision (so there was no net change in kinetic energy, and any energy used to accelerate the cars went into the collision). In this way of doing the calculation, by focusing on changes in the total kinetic energy (which are invariant under a change of frame), you can see you will get the same answer in any frame, but your work is more difficult if you don't use the special rest frame at which both cars are initially at rest.
Throughout this answer, I've assumed that we are discussing inertial frames. However, neither car is in an inertial frame throughout the process, because there is some acceleration (both initially and during the collision). You can also analyze the scenario using the non-inertial reference frame of one of the cars. But, the analysis will be more complicated, because there will be changes to the total kinetic energy in the non-inertial frame during the times when the frame is accelerating. This is a "fictitious" change in energy, due to work done by the "fictitious" forces in the non-inertial frame. If you correctly account for these changes, you will get the same result as the analysis done in an inertial frame. As you can see, you can always get the same result as the analysis done in the privileged initial rest frame of the cars, but at the cost of increasingly elaborate forms of bookkeeping.
A: Repeating what others have said, but, I think, making it more clear:
After Case I, the debris' center of mass has a velocity of $2v$. But Case II ends with the center of mass having a velocity of $0$. So Case II does not, in fact, result in the same event as Case I. To get Case II to have the same ultimate result as Case I, we have to accelerate the debris, which has mass $2m$, to velocity $2v$. This require energy of $2E$. So the total amount of energy required in each case is the same.
