What's wrong with this argument that kinetic energy goes as $v$ rather than $v^2$? Trying to non-technically explain why (kinetic) energy goes as $v^2$ rather then the perhaps-more-intuitive "double the speed, double the energy" $v$, I ended up putting my foot in my mouth (itself a difficult physical manipulation:) by "proving" precisely what I didn't want to prove, as follows.
Suppose you get an object moving to speed $v$. That'll require some amount of energy, which we'll just call $E_v$ (we won't need to bother calculating it). Now, to somebody else, moving alongside that object, it seems to be stationary. So he can get it moving at $v$ relative to himself with the same energy $E_v$ that you used to get it moving at $v$ relative to yourself.
So the total energy used is $2E_v$, first to get it moving from $0$ to $v$ relative to you, and then to get it moving from $0$ to $v$ relative to that other guy. But now it's moving at $2v$ relative to you, and the total energy used is $2E_v$ rather than the known-right answer $4E_v$.
So what's wrong? I'm guessing it's somehow got to involve those two different lab frames. For example, maybe whatever apparatus the second guy used in his frame first had to acquire it's $v$ relative to your original frame, and that required some energy. But even so, why exactly an extra $2E_v$ (to make up the "missing" difference)? So that can't be precisely the argument's error. But it's the two frames, somehow. Right? Or what?
>>Edit<< This is an extended reply to @StephenG's comment under @PhilipWood's answer below. Stephen: sure energy's a common-sense concept -- everything in physics is (must be) common sense if you can get to the underlying intuition. And after failing miserably with my above-described argument, I came up with a more successful attempt, described below just to prove my point that it ultimately must be common sense. This argument's a bit more elaborate, and I'd like to come up with a correct simpler one. But at least this argument gets the correct result...

Suppose you're hit with a ball going at speed $v$, and then with an identical ball going at speed $2v$. So how much "harder" does the $2v$ ball hit you?
To answer that, suppose the balls are made up of lots and lots of closely-packed identical little particles, all moving side-by-side together. Then each little $2v$-particle carries twice the "punch" of a $v$-particle ("punch" here is, of course, momentum, not energy, but I just said "punch" to avoid introducing big words and unnecessary technicalities).
However, since the $2v$-particles are travelling twice as fast, then in, say, one second, twice as many of them will hit you. Therefore, you'll be hit with twice as many particles, each carrying twice the "punch". So your "total punch" will be four times as great, not two times.
Okay, so this argument involves time, and therefore power rather than energy. So it's not entirely 100% achieving its purpose. But since this was a non-technical discussion, I simply didn't bother mentioning my misgivings about it. Good enough for the time being, I figured.
But, to elaborate my original question, can you make air-tight the above argument, and maybe explain what's wrong with the original one (hopefully so that it's correct and even simpler than this one)?
 A: This question was actually settled experimentally in the $18^{\mathrm{th}}$ century in arguments over what quantity deserved the title "vis viva" (see also, this discussion on StackExchange). Long story short, the argument was settled by experiments conducted by Willem 's Gravesande and elucidated by Émilie du Châtelet. Those experiments showed, basically, that the amount you could deform clay by dropping a heavy ball into it depends on what we now call kinetic energy, $\frac{1}{2}mv^2$, not momentum.
The tricky thing, of course, is that the kinetic energy content of an object is observer dependent, and failing to take that into account is where you're running wrong with statements like "So the total energy used is $2E_v$"; you're adding kinetic energies observed by different people who are in different reference frames, and you can't do that. The Mythbusters actually ran head-long into this trap in a slightly different way in an episode about head on collisions with semi-trucks when one of them said that head on collisions were 4 times more dangerous than hitting a brick wall because there was 4 times the energy involved. They were thinking in terms of one of the drivers who sees double the approach speed, and therefore 4 times the energy. When they went back and tested that statement using colliding pendulums with clay on them, they found that there was only twice the energy in the collision, and that the deformation in the equal head-on collision is the same as the "running into a wall" one. 
The reason? It's because to harvest the $4\times$ energy that the truck observers think there is, the collision would have to end with both trucks moving to the right (or left) with the initial speed of the right-bound (left-bound) truck. Because they both end the process in the Earth frame, the Earth frame is the one that assessed the kinetic energy available correctly. This is why in special relativity we focus so much on the "invariant mass" in collisions - that is the part of the energy that is actually available to do stuff during the collision, and all observers agree on it. 
Specifically, if you have objects labeled $1$ and $2$ on a collision course, then the energy available to deform/heat the objects (or create new particles in a particle collider) is
\begin{align}
 E_{\mathrm{COM}} &= \sqrt{(E_1-E_2)^2 - \left(\vec{p}_1-\vec{p}_2\right)^2 c^2} \\
    & = \sqrt{\left(\sqrt{\vec{p}_1^2c^2 + (m_1c^2)^2 }-\sqrt{\vec{p}_2^2c^2 + (m_2c^2)^2 }\right)^2 - \left(\vec{p}_1-\vec{p}_2\right)^2 c^2},
\end{align}
where $E_{\mathrm{COM}}$ is the energy in the center of mass (or momentum) frame.
Of course, that expression includes the mass energy. To make it useful for situations where that doesn't change you have to subtract off $m_1c^2$ and $m_2c^2$ to get the "kinetic" energy. That produces
\begin{align}
K_{\mathrm{COM}} & = \sqrt{(m_1 c^2)^2 + (m_2 c^2)^2 + 2 \vec{p}_1\cdot\vec{p}_2 c^2 - 2 E_1 E_2 } - m_1 c^2 - m_2 c^2.
\end{align}
Getting a low speed approximation of $K_{\mathrm{COM}}$ is a long process that has to be handled carefully because the square root function is not analytic near $0$. As the name suggests, though, it is the kinetic energy observed by someone who is in the center of mass frame the entire time, so we can do the derivation in the low speed limit from the start using
$$\vec{v}_{\mathrm{COM}} \equiv \frac{m_1\vec{v}_1 + m_2 \vec{v}_2}{m_1 + m_2}$$
producing (using Galilean transformations)
$$K_{\mathrm{COM}} = \frac{m_1}{2} \left(\vec{v}_1 - \frac{m_1\vec{v}_1 + m_2 \vec{v}_2}{m_1 + m_2}\right)^2 + \frac{m_2}{2} \left(\vec{v}_2 - \frac{m_1\vec{v}_1 + m_2 \vec{v}_2}{m_1 + m_2}\right)^2. $$
While the formula is considerably more complicated, every observer agrees that when $m_1$ and $m_2$ collide, this is the amount of energy available to "do stuff" because nothing $m_2$ and $m_2$ can do, in isolation, can affect how their center of mass is moving relative to everyone else (without interacting with the rest of the universe or throwing off some mass/energy, $m_3$).
A: Start with a decent definition of kinetic energy. I'd go for "The KE of a body is the amount of work it can do in coming to rest". Then consider something like a laden sledge of mass $m$ moving at speed $u$ on level ground. Imagine it being brought to rest by someone pulling on a rope attached to it. If you assume the sledge's deceleration to be uniform (to make life easy) then, using $W=Fs$, $F=ma$ and $v^2=u^2+2as$, you should be able to show that the amount of work the sledge does is $\frac{1}{2}m u^2$.
A: In general, neither energies nor energy differences are invariant between frames. But conservation of energy is true in all frames, and we can use that to figure out where the problem is.
To recap, the person in the moving frame spends energy $E_v$ from their muscles to raise the kinetic energy of the object by $E_v$, which is just fine. The person in the original frame agrees the person in the moving frame spends energy $E_v$ from chemical energy in their muscles (everybody agrees on how hard somebody is breaking a sweat) and raises the kinetic energy of the object by $3 E_v$. 
The extra $2 E_v$ of energy comes from the fact that the moving person started with a reservoir of kinetic energy: that of their own body, which is moving at speed $v$. This energy is reduced because the person slows down due to Newton's third law; it is "harvested" to be put into the object.
There's no way to avoid putting in this extra energy. If you try to reduce the change in speed by putting them in a large car, the energy comes from the kinetic energy of the car; the argument is just the same. If the car's speed is fixed too, the energy comes from the chemical energy of the gasoline. The very same explanation holds for a rocket, where this is called the Oberth effect. In all cases, there's no contradiction in taking energy to be quadratic in speed.
In case you're not convinced, here's an explicit calculation. We'll make the person's mass infinite for convenience. The loss of kinetic energy of the person is 
$$\Delta K = \frac{dK}{dp} \Delta p = \frac{p}{M} m v = m v^2 $$
where I used $K = p^2/2M$ for the person's kinetic energy. But this is just $2 E_v$ as stated above.
A: What would you say to a man who thinks climbing a flight of stairs is too exhausting, so he walks around the mall for an hour looking for an elevator?

There's a bit of intuition (fear of heights, etc) which seems to be baked into our psyches from birth, but the overwhelming majority of the intuition we have is intuition we build.  We get a rough feel for velocity because we walk, jog, and sprint.  We get some idea of force because we push on rocks and each other.
Nothing that the average person does gives them a feel for work and energy.  Indeed, intuition is often precisely in the other direction.  Tell somebody holding a heavy piece of furniture off the ground that they're not doing any work on it, and they may deliberately drop it on your foot.
In your explanations of kinetic energy, you invoke (implicitly) work, power, impulse, and changes in reference frame.  Every one of those concepts (and especially the last one) is more complicated than the notion of kinetic energy.  Have you ever seen the video where Feynman argues with a reporter over his explanation of magnetic repulsion?  This is almost precisely what he was talking about.
It's possible to give hand-wavy arguments as to why kinetic energy is quadratic in velocity.  You could argue that it takes four times as much effort to lift an object to a height $4h$ than it does to lift the same object to a height $h$, so in the former case the object has four times as much energy - but would hit the ground with only twice as much speed (why?  This might take another hand-wavy explanation).

But to be honest, I think the best approach would be something like this:

There is a quantity called "kinetic energy" which reflects how
  difficult it is make an object of mass $m$ to move at a speed $v$ - or
  conversely, how difficult it is to stop it once it's already moving. 
  Mathematically, it is equal to $\frac{1}{2} m v^2$, which just means
  that doubling the mass of the object doubles the energy, but doubling
  the speed of the object quadruples the energy.
If you want to know more about it (why the factor of $\frac{1}{2}$?
  Why $v^2$ and not $v$?), then I would be happy to prepare a few
  discussions to explain it to you.  Just be warned - it will take a
  while, and we'll have to dust off the old algebra skills for some of
  it.

A: In classical mechanics the laws of motion don't change in time. (For example, Newton's first law is as true at 8 o'clock in the morning as 8'clock in the evening). This means that mathematically you can find a quantity (for any set of objects) that remains the same regardless of the time. The quantity is defined as Energy and it is useful only because it must be conserved.
For this question ignore the idea of potential energy etc. and let's focus on the kinetic energy which we want to be conserved regardless of the time. In classical mechanics the motion of a set of objects can be fully defined using position (x,y,z) velocity v and time t. The kinetic energy must be a function of these variables. It can't depend on time (obviously or it won't be conserved), it can't depend on it's position (space is the same from place to place), it can't depend on velocity (because velocity has a direction and the kinetic energy should remain the same regardless of time and so can't depend on the direction an object is travelling in). Kinetic energy dependence of $v^2$ will work because $v^2$ is a scalar.
In your example, you have defined a quantity which is dependant on velocity - it isn't the kinetic energy because it won't be conserved through time. The quantity you have defined doesn't have any useful associated conservation law and so isn't useful when applying maths to classical mechanics problems. (Incidentally, the quantity you have defined in your question and called 'kinetic energy' is a vector not a scalar).
