The faster you move, does it take more and more energy to increase your speed at the same rate? I'd like to confirm this somewhat counterintuitive result. Starting with the definition of kinetic energy:
$$E = \frac{1}{2} mv^2$$
Assume a vacuum, no external forces, and starting from rest. Adding some energy $E$ to the system by burning some fuel (by firing a rocket, etc.), the following should be true.
$$\frac{1}{2} m{v_1}^2 = \frac{1}2 m{v_0}^2 + E$$
Solving for $v_1$,
$$v_1 = \sqrt{{v_0}^2+\frac{2E}m}$$
If $E$ remains constant, by burning fuel at a constant rate, $\Delta  v$ decreases as $v$ increases.
 A: Yes, that's right, you can also differentiate both sides of
$$\frac{1}{2} mv_1^2 = \frac{1}2 mv_0^2 + E$$
with respect to time and putting $\frac{dE}{dt} = P$, the power supplied, you get to
$$mv\frac{dv}{dt} = P$$
so for a given power $\frac{dv}{dt}$ is inversely proportional to $v$
A: The algebra is correct, but the interpretation may not be what you intend. In your description, there is a contradiction between "no external forces" (conserved momentum) and changing velocity from $v_0$ to $v_1$ (non-conserved momentum).
You refer to a "rocket" that is "adding some energy $E$ to the system by burning some fuel". A rocket is more complicated to analyze than what you are showing, because the "system" (on which there are no external forces) is the rocket plus its propellant. The system is not moving as a rigid body and cannot be described by a single mass and velocity, so your equation does not apply. The energy $E$ released by burning is the net increase in kinetic energy of rocket plus propellant, but this may be distributed in different ways between the two.
A simpler application of your approach would actually be when a vehicle is subject to external forces, but the thing that momentum is exchanged with is so massive that its energy change is negligible -- say, the Earth. Take an idealized wheeled land vehicle with only static friction (tires gripping the road), with no rolling resistance or drag, and with a perfectly efficient engine and transmission. Then your formula does apply directly: The kinetic energy of the vehicle increases by the energy $E$ of fuel burned.
A: You are correct that adding kinetic energy at a constant rate will result in less and less increase in velocity as $v \propto \sqrt{\text{KE}}$. However, burning fuel increases the momentum, rather than kinetic energy, at a constant rate, because the fuel is ejected in the opposite direction with constant exhaust velocity with respect to the rocket.
If we assume that the mass of the rocket and remaining fuel remains approximately constant, the velocity will also increase at an approximately constant rate. However, if we account for the decreasing mass of the rocket, the velocity increases at a faster and faster rate. Either way, this results in the rocket gaining kinetic energy at a faster and faster rate since kinetic energy is quadratic in velocity.
A: We can rewrite your analysis in a slightly different way:
The energy $E$ you need to go from speed $v$ to speed $v+\Delta v$ is
$$E = \frac{1}{2}m (v+\Delta v)^2 - \frac{1}{2} mv^2$$
which we can expand as
$$E=\frac{1}{2}m[v^2+(\Delta v)^2+2v\,\Delta v-v^2] = \frac{1}{2} m[(\Delta v)^2+2v\,\Delta v]$$
so that, as you mentioned, the energy you need to go from $v$ to $v+\Delta v$ depends on the initial value $v$ through the term $\propto 2v\,\Delta v$.
If your energy input $E$ is constant, of course over time you are going to get a decreasing value of $\Delta v$.
If you then burn energy at constant power $P$ so that you produce your total energy $E$ in a time $\Delta t$ then
$$P\Delta t = (1/2) m\,[(\Delta v)^2+2v\,\Delta v]$$
is the equation connecting all terms together: at constant power it will take a longer time to reach a given $\Delta v$ at higher initial speeds, etc.
Notice also that in the limit $\Delta t\rightarrow 0$ and thus $\Delta v \rightarrow 0$ you would get the same result from John Hunter's answer, i.e.
$$P = \frac{1}{2} m {(\Delta v)^2 \over \Delta t} + mv{\Delta v\over\Delta t}\rightarrow mv {\text{d}v\over \text{d}t}$$
as ${\Delta v^2 \over \Delta t} \rightarrow 0$ because of the squared value in $\Delta v$.
We can also solve it, getting that your speed over time at constant power is given by
$$v{\text{d}v\over \text{d}t} = {P\over m}$$
so that (solving the differential equation - but it is the same as solving conservation of energy as you did...!)
$$v^2(t) = v^2(0)+{2P\over m} t$$
i.e.
$$v(t) = \sqrt{v^2(0)+{2P\over m} t}$$
so that the speed always increases but with a square-root behavior, i.e. slowlier over time.
A: The other answers are right (+1 to each). But it may help your intuition to consider the total energy and momentum changes of rocket + exhaust gases.
Suppose a rocket is sitting at rest in your favorite frame. It fires its engine briefly, shooting a pulse of exhaust backward, and propelling itself forward. The exhaust has $m_1$ and $v_1$, leaving the rocket with $m_2$ and $v_2$.
$$\vec p_{before} = \vec 0$$
so
$$\vec p_{after} = m_1 \vec v_1 + m_2 \vec v_2 = \vec 0$$
or, just using magnitudes,
$$m_1 v_1 = m_2 v_2$$
Also
$$\Delta KE = \frac{1}{2}m_1v_1^2 + \frac{1}{2}m_2v_2^2$$
Now suppose the rocket has acquired velocity v, and repeat the experiment. Assume the rocket still has mass $m_2$. Since we know the directions, we will just use magnitudes.
$$p_{before} = (m_1 + m_2) v$$
$$p_{after} = m_1 (v - v_1) + m_2 (v + v_2) = p_{before} + m_2 v_2 - m_1 v_1$$
Again
$$m_1 v_1 = m_2 v_2$$
For energy,
$$\Delta KE = \Bigl[\frac{1}{2}m_1(v-v_1)^2 + \frac{1}{2}m_2(v+v_2)^2 \Bigr] - \frac{1}{2}(m_1 + m_2) v^2$$
$$= -m_1vv_1 + m_2vv_2 + \frac{1}{2}m_1 v_1^2 + \frac{1}{2}m_2v_2^2 $$
$$= \frac{1}{2}m_1v_1^2 + \frac{1}{2}m_2v_2^2$$
A: Yes, the change in energy is the work, which is force times distance. Change in velocity is proportional to change in momentum, change in momentum is impulse, and impulse is force times time. If the force is constant, and we consider a fixed amount of time, then as the velocity increases, the impulse remains constant, but the distance traveled over that time increases, as so the work also increases. This also means that if we take the limit as $t$ goes to zero of change in energy per time, it goes to zero; at the instant you start accelerating, the power is zero.
A: Since nobody mentioned it yet, maybe Tsiolkovski's equation would be worth considering.
Propeller mass is the critical factor in increasing a rocket speed, that's the key to the delta-v budget used in space travel.
If you factor in the way a rocket engine works, i.e. ejecting reaction mass at a constant rate and speed, your equation (that assumes a constant mass) no longer holds. That might be the reason why your result seems counter-intuitive: motors of space vehicles don't work that way (except in Star Wars maybe, where a X-Wing that can hardly have room for more than a few tons of fuel can achieve orbit - and a jump into hyperspace to boot - with that ridiculously small amount :) ).
Rather than an unchanged object to which a constant energy is added, a rocket is an object of ever decreasing mass to which a constant impulse is applied. A tiny payload sitting atop a huge fuel tank and engines that only add to the final dead weight.
In terms of energy, what you end up doing is consuming a huge quantity of chemical energy to accelerate the fuel you'll eventually dump into space to recover only a fraction of that energy.
At a given moment, if M is the mass of remaining fuel, the energy 1/2 MV² you spent accelerating it has been a net loss. All you can hope is recover some energy when you start burning it.
An ideal rocket engine could adapt its ejection speed to "drop" the reaction mass just outside the reactor with zero kinetic energy in a referential tied to the launchpad (i.e. at the opposite of the current rocket speed, in a local referential), thus transferring 100% of the energy to the rocket and 0% to the exhaust gasses.
Alas, all we can manufacture is constant impulse engines, so when an amount of reaction mass is ejected, some kinetic energy goes away in a puff of exhaust gasses and the rocket doesn't get back 100% of the energy released by the engine.
The example of the space shuttle given in the wiki is quite telling. Even accounting for the cost of potential energy, the vast majority of the orbiter energy comes from the speed increase (0.2 TJ vs 3TJ : 15 times more kinetic than potential energy). Even accounting for air resistance and potential energy needed to lift the whole shuttle and its remaining fuel, at least 3/4 of the energy is spent accelerating the fuel itself.
A: It is true that to maintain a constant acceleration that increases its speed relative to a rest frame, a rocket needs to spend increasing amounts of energy relative to that rest frame.  Conservation of energy tells us this.
It is also true that a typical rocket (in space, assuming no outside forces) accelerates at a constant rate.
It is also true that a typical rocket uses chemical energy at a roughly constant rate.
But this seems impossible!  The rocket accelerates at a constant rate, and to do this it must also increase the rate at which it uses energy, but it uses chemical energy at a constant rate.  How can we reconcile these three facts?
The first piece of the puzzle is that the rocket will run out of fuel and reaction mass before it starts breaking conservation of energy.  The rate it gains kinetic energy relative to the rest frame can never be greater than the rate it uses energy relative to the rest frame, and it must run out of fuel before that time.
The next piece of the puzzle is that when the rocket is going slowly, it is using its chemical energy very inefficiently.  We know it must be, because the rate of kinetic energy increase is proportionally slower at low speeds, while the rocket's rate of use of chemical energy is the same.  So, it has more power generation initially than it "needs" to increase its kinetic energy.  The rocket is initially running well under its power capacity, and as it speeds up it starts to use the power more and more efficiently to increase its K.E., up until the point where it runs out of fuel.
Let's imagine a rocket that has a 100 kg payload and carries 900 kg of reaction mass.  It begins stationary in space with no external forces acting on it.  It constantly throws 1 kg/s of reaction mass backwards at 1000 m/s relative to itself.  This means the reaction mass exerts a constant force of F = 1000 kg m / s^2, or 1000 N, on the rocket.  It also means that the power exerted by the rocket, in the rocket's frame, is 1/2 * 1 kg/s * (1000 m/s)^2 = 500 kW.
The velocity of the rocket at time $T$ is $v(T) = \int_0^T a(t) dt = \int_0^T 1000 / m(t) dt = \int_0^T 1000 / (1000 - t) dt = 1000 (-\ln |1000 - T| + \ln |1000|)$
The velocity of exhaust (in the initial stationary frame), $v_e(T)$, is always $v(T) - 1000$ m/s.

The energy of the rocket at time T is $1/2 m(T) v(T)^2$.
The total energy of the exhaust at time T is obtained by integrating over the energy of each piece of exhaust.  It is $\int_0^T 1/2 v_e(t)^2 dt
= 1/2 \int_0^T (1000 (-\ln |1000 - t| + \ln |1000|) - 1000)^2 dt$.

The total power output is obtained as the rate of increase of kinetic energy of rocket + exhaust.  We already knew this should be 500 kW, and indeed it is.
The effective power output is the rate of increase of kinetic energy of the rocket.  This is small at the beginning, as most of the kinetic energy is going into the exhaust, then increases to a maximum when the rocket is going 1000 m/s (because at this instant none of the energy is going into the exhaust, because the exhaust is stationary in the initial frame), and then decreases again as the rocket accelerates further.  It actually goes negative at the end because the rocket is losing mass "more rapidly" than it is accelerating.

