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.
