Why work to change velocity from 0 to 20 km/h is less then from 20 to 40? Imagine spaceship in vacuum with mass = 1. At beginning, it has velocity 0, and kinetic energy 0. 
$$W_1 = 0$$
Then, it turns on its engine, and changes velocity from 0 to 20 (delta v = 20). It's kinetic energy became:
$$W_2 = \frac{1}{2}mv^2 = \frac{1}{2}\times 1\times 20^2 = 200$$
$$W_2 - W_1 = 200$$
Then, it turns on its engine, and changes velocity from 20 to 40 (delta v = 20).
$$W_3 = \frac{1}{2}\times 1\times 40^2 = 800$$
$$W_3 - W_2 = 400$$
Question: why $W_3-W_2 > W_2-W_1$?  I intuitively feel that if we turn engine at any moment on some time t = const (so, engine will make some work A = const), spaceship velocity will change to some $\Delta v$ = const. But, looks like this is wrong. $\Delta v$ will depend on velocity at moment of engine turning on (because $\Delta W$ depends on it and A is const). What is difference for engine, moving spaceship with velocity 0, or 20, or some another?
On this logic, if we turn on engine forever, spaceship will lose acceleration with time, and in time converging to infinity acceleration will become 0. Then spaceship will achieve max possibly velocity, and working engine will do nothing at all (i.e. make $\Delta v \to 0$). It is strange, but is it right?
 A: One needs to spend more energy to accelerate a faster object by $\delta v$ because of your derivation based on kinetic energies (which go like the velocity squared, and that's more quickly increasing than proportionality $v$) or, equivalently, because the work per unit time (power) is
$$ \frac{dE}{dt} = \vec F\cdot \vec v$$
The force $\vec F = m\vec a$ is the same, regardless of the velocity, for a fixed acceleration. However, when the object is already faster, it travels a longer distance per unit time, and $dE = \vec F\cdot d\vec x$ where $d\vec x = \vec v\cdot dt$. Because of the extra factor $\vec v$ in the displayed formula above, the energy spent per unit time grows with the velocity if the acceleration is constant. 
Here, it may be useful to stress that the work/energy goes like $dE=\vec F\cdot d\vec x$ and not, for example, $dE\neq \vec F\cdot dt$. It's not hard to see why the latter has to be wrong. It's, for example, because $dt$ is a scalar so its multiplication by $\vec F$ would yield a vector, not a scalar as required for its being $dE$. Also, one knows $dE=F\,ds$ from the everyday life experience, e.g. from elevators. If you want to lift an elevator of some weight $F=mg$, the work is proportional to the distance (height difference) and independent of time. It doesn't matter how quickly you do the work. (Using muscles, we may have the misleading impression that one needs to spend energy even for holding an object, but this useless work may be saved using a pedestal or counterweight, in the elevator example.)
In a later part of the answer, you may be implicitly referring to the Galilean invariance of the laws of physics: they don't really change if you switch to a different inertial system, one that is moving by motion with the constant direction and velocity relatively to the original one.
However, when we're switching to a different inertial system, the energy is not preserved. It's not hard to intuitively understand why the energy has to change if we switch to a different inertial system. After all, even for one object, the energy contains the kinetic energy that does depend on the velocity, so it must also depend on the frame because the velocity does depend on the frame. Paradoxically enough, the explicit description what happens with energy is simpler in special relativity where the energy is simply mixing with the momentum if we switch to a different frame; however, $E=Mc^2$ must be included in the total energy.
In non-relativistic physics, the transformation of the energy induced by a switch to a new inertial frame is a bit more awkward. When the energy is $E$ in one frame, then in the frame that is moving by velocity $\vec V$ relatively to the original one, the energy is
$$ E' = E + \vec P\cdot \vec V + \frac 12 M |\vec V|^2 $$
where $\vec P$ is the total momentum and $M$ is the total mass of everything. Note that both $\vec P$ and $M$ are conserved so the conserved energy $E$ just gets mixed with two other additional conserved quantities under the Galilean transformation (switching to a differently moving coordinate system). In relativity, $E=Mc^2$ so the conserved quantities $E,M$ are not independent.
So if you consider an object that is already fast and you switch to its rest frame, the energy will be increasing very slowly for a constant acceleration. However, in the original frame, the energy has the extra term $\vec P\cdot \vec V$ which is increasing with $\vec P$ in a way that grows faster with $\vec V$. It's this middle term that yields the same outcome as the derivations above: the power has to be larger for a fixed acceleration if the velocity is already higher.
The term $M|\vec V|^2/2$ doesn't play a role here because we're considering fixed inertial frames only and $\vec V$ is, much like this whole term, constant. Only $\vec P$ is changing as the object keeps on accelerating.
