How can kinetic energy be proportional to the square of velocity, when velocity is relative? Let's start with kinetic energy (from los Wikipedias)

The kinetic energy of an object is the energy which it possesses due to its motion. It is defined as the work needed to accelerate a body of a given mass from rest to its stated velocity. Having gained this energy during its acceleration, the body maintains this kinetic energy unless its speed changes. The same amount of work is done by the body in decelerating from its current speed to a state of rest. In classical mechanics, the kinetic energy of a non-rotating object of mass m traveling at a speed $v$ is $\frac{1}{2}mv^2$.

Let's say you & your bike have mass of 100kgs, then your kinetic energy at 10m/s would be
$$ E_a = 1/2 \times 100 \times 10^2 = 5000J = 5kJ$$
If you apply another 5kJ of energy, you don't get to 20m/s though, you only get to:
$$ E_b = 10000J =1/2 \times 100 \times V_b^2$$
   $$\implies V_b = \sqrt{10000 / (1/2 \times 100)}
        = √200
        = 14.14m/s$$
Let's say you and a buddy are both coasting along at 10m/s though, from their perspective you've just burned 5kJ but only accelerated 4.1m/s, even though you seemed stationary.
Imagine you and your mate are in space drifting along together, at an unknown speed. Your mate fires his burners and accelerates away from you. There's a big screen on his ship showing how many joules of energy he just burned, and you can measure his resulting relative velocity just fine.
The question is, Will 5kJ of energy always produce 10m/s of relative velocity,,assuming 100kg spaceships?
If 5kJ always produces 10m/s, Why does the second 5kJ only produce 4.1m/s? What is going on here?
 A: Note that over here, the "burners" produce acceleration by expelling fast-moving mass. The conservation of momentum leads to the ship going faster. Both observers will measure the same change in velocity.
However, someone in a "stationary" frame (or any other frame with a different velocity) will measure the same change in velocity but a different change in energy. Velocity, energy, and momentum are all relative, but for inertial frames velocity and momentum are linearly relative (so we can add or subtract a constant for a given transformation), while energy is quadratic.

Assuming 100kg spaceships, will 5kJ of energy always produce 10m/s of relative velocity?

In this case, where the initial relative velocity is 0, yes. But not in general, because if they start off with a different
A: 
How can kinetic energy be proportional to the square of velocity, when
  velocity is relative?

Without reading the rest of your question, I must first reply that one has nothing to do with the other.
Kinetic energy is frame dependent, just as velocity is.
Momentum is proportional to velocity and is frame dependent too, just as velocity is.
Now, looking at the body of your question:

Imagine you and your mate are in space drifting along together, at an
  unknown speed.

Unknown speed relative to what?  Unknown speed relative to Earth?  Unknown speed relative to the solar system?  Unknown speed relative to the CMB?

Assuming 100kg spaceships, will 5kJ of energy always produce 10m/s of
  relative velocity?

Relative to what?  Relative to the initial inertial frame of reference before the acceleration?  Or relative to some frame of reference in some arbitrary relative motion?
(The point of all these questions is to prompt you to think more clearly about your question in the hope that you'll come to the answer yourself...)
A: The space bicycle paradox
(also known as "The Shadoks go to space" or "How to walk in space")
I think this is a cute question. Though the style is a bit awkward
regarding frames and speed, it is presented as an interesting
paradox. In a nutshell the question is the following (simplifying
details):
If I am driving a spaceship, inertial frame invariance tells
me that I get the same velocity increase for each new unit of energy
used for accelerating motion. But if I am on Earth riding a bicycle, I
get less velocity increase for each new unit of energy spent on
accelerating. Why is it different ?
Of course details matter, and there must be a fallacy somewhere,
which we identify by analyzing the details of the examples. The poster
is obviously aware that there is a fallacy, but has difficulty
unknotting it in the contexts in which it is stated.
Though it can possibly be construed as such, I disagree with the view that
this question as purely a frame issue. The paradox is much more a momentum
conservation issue, probably originating from a pedagogical problem,
as momentum is often ignored in collision-less exercises taking place
on Earth surface.
Typically, in problems taking place on Earth, we tend to forget
Earth. But it is there. Fortunately !   
High speed is hard on a bicycle (why ?)
The question considers two bicycles A and B, that each accelerate a
first time with a given amount of energy, and then A accelerate again
with the same energy. But A does not double its speed, he only
multiplies it by $\sqrt{2}$. Hence its speed increase with respect to B
is only about 0,414 of its first speed increase from immobility on the
ground.
Let's analyze the case of the bicycles. This is all linear, so I
forget about vectors. And we simply do a mostly qualitative analysis
to understand what happens. The rest is just applying formulae.  I
will assume, to abusively simplify things, that the local surface of
Earth is an inertial frame for the small duration of the experiement (it is an often used approximation).
So we take the local ground as inertial frame for a first analysis.
Suppose the first acceleration from $v_0=0$m/s to $v_1=10$m/s used a
force $F$ applied on a distance $d$ for a time $t_1$. Each bicycle
gained a momentum $Ft_1$ and a kinetic energy $K=Fd$ with respect to
their initial frame: Earth ground.
Now bicycle A accelerate again, with the same amount of energy. It can
do that by applying the same force $F$ over the same distance $d$ on
Earth surface. Since it already has speed, the distance $d$ will be
covered in a shorter time $t_2$. So this acceleration will give it
less momentum $Ft_2$, than the first one, which explains that the
speed gain will be lower.
But if we do the same analysis with respect to buddy bicycle B,
things are different. While A is accelerating the second time, buddy B
is moving, and actually covering a distance $v_1 t_2$. So the distance
covered by A with respect to B during the second acceleration is only
$d-v_1 t_2$. Hence the energy spent accelerating is, from the point of
view of (frame) B, $K_B=F(d-v_1 t_2)$ which is clearly less than
$K=Fd$.
But you "know" you spent energy $K$, and some of it has disappeared
from B's point of view. Where is the energy gone ? Well, from B's
point of view, he is not actually moving: we are all motionless with
respect to ourselves.  When A was coasting along, he was also
motionless with respect to B, until he accelerated again. It was the
Earth that was moving under the two bicycles at speed $v_1$, in the
opposite direction.
When, A accelerated, he applied a pushing force on the ground to go
forward, which was balanced by a friction (reaction) force from the
ground. It is the reaction force that does the work accelerating A
over a distance. In the Earth frame. Earth is not moving so that no
force attached to Earth does any work. But in buddy B frame, the Earth
is actually moving backward. The friction force of A acceleration
increases the momentum of A, and this increase has to be stolen
somewhere (total momentum does not change). So it has to come from
Earth, i.e. from a change of the speed of Earth surface (do not worry,
it will not cause earthquakes, as shown by answers to several questions on this
site). The missing part of the energy has been used to accelerate the
Earth motion with respect to B.
High speed is easy in space (is it?)
Taking the same problem to space, as much as make sense (you will see
why), may clarify some issues. But it is really quite different.
The only way to accelerate is to exchange momentum with another
mass. Other than direct use of the natural force fields (such as
gravity), the usual way to do that is by exhausting a reaction mass at speed from
a rocket engine. You throw the mass one way, and you are pushed the
other way with the inverse momentum variation. Since you carry the mass, the trick
is often to increase the exhausted momentum by using high speed with small masses, so
that you do not end up massless too quickly (unless you are a top
model).
You may have a screen dial telling you how much energy you spent. But
that is of limited use because it will not tell you what you spent it on, as
you are accelerating both your craft and the exhausted reaction mass. The
repartition of energy is controled by momentum preservation so that we
have in the initial inertial frame (as is well known):


*

*momentum conservation : $m_c v_c+m_r v_r=0$

*kinetic energy : $1/2(m_c v_c^2+m_r v_r^2)= W$
where indices $c$ and $r$ are respectively the craft and the exhausted reaction
mass, and W is the energy spent. Note that initially the craft mass
is $m_c+m_r$ as the craft is carrying the reaction mass to be exhausted.
If you analyze it from another inertial frame B going initially at a
speed $v$ with respect to the craft), you find out that the kinetic
energy variation is again $W$, though the total kinetic energy includes
another term $(m_s+m_r)v^2/2$ which is the initial kinetic energy of the
craft in inertial frame B.
We can now address the first question:

Will 5kJ of energy always produce 10m/s of relative velocity,
    assuming 100kg spaceships?

The answer is almost yes (in classical mechanics), provided all other
things on board are kept equal.  What is true is that the craft will always gain the same
amount of velocity with respect to its previous inertial frame, provided it spends its energy in the same way. What
else would inertial frames be for$\,$?
However, the magnitude of that velocity will be less than 10m/s because the energy spent has to be shared as kinetic energy between the spaceship and the exhausted reaction mass. The sharing ratio remains open with the data provided here, and so does the velocity increase.
Since all inertial frames have constant velocity with respect to each
other, and since velocities add vectorially in classical mechanic, I
guess all that remains true in all inertial frames.
But as I said, this is true if all other things are kept equal on
board. We assumed that somehow the ship mass is kept constant (mass is
maintained by transfer from another craft: spatial refueling ?). The
other thing that must be kept unchanged is the ratio of energy
repartition between the ship acceleration and the exhausted mass
acceleration, as measured in the inertial frame of the ship just
before acceleration. Of course, this inertial frame changes with each
acceleration.
Actually the energy is shared in proportion to the respective speeds
of ship and exhausted reaction mass in the ship inertial frame before
acceleration. If you multiply by $v_c v_r/2$ in the momentum conservation
formula, you get $K_c v_r + K_r v_c =0$, where $K_c$ and $K_r$ are
kinetic energies. It follows that $K_c/K_r=-v_c/v_r=m_r/m_c$, the last equality resulting directly from the momentum conservation formula.
Seen from the ship, the energy sharing is controlled by controlling exhaust speed (or exhausted reaction mass). So assuming the change of mass negligible, the answer to the question is yes, for 5kJ of energy, the speed will always increase by the same amount, though it is less than 10m/s in magnitude, provided the exhaust speed is not changed. It is speed rather than velocity, as the craft could change its orientation.
Back to Earth
This leads to the second question:

If 5kJ always produces 10m/s, Why does the second 5kJ only produce
    4.1m/s?

Well, that was true for the bicycle, and, as hinted before, the
situation is slightly different, because the reaction mass is Earth
itself.
When the bicycle is initially at rest in the Earth ground frame, it
was as if the Earth was a reaction mass carried by the bicycle (aren't
you strong ?). When the bicycle is accelerated by pushing on Earth,
the mass on the planet is such that it essentially does not move in
its initial frame, while the bicycle does, however slow. So, if we consider
the energy sharing ratio formula above, the speed ratio $v_c/v_r$ is
practically infinite because $v_r$ is quasi null. The same is then true of the energy ratio
$K_c/K_r$, so that all the energy goes to the bicycle, and none to the
planet. And this is the reason why the bicycle accelerates to 10m/s, converting all the energy into kinetic energy.
But the situation is different for the second acceleration. In the
case of the spaceship, it is carrying its reaction mass at its own
speed. But in the case of the bicycle, the second acceleration is
obtained by pushing on a reaction mass that is moving with respect to
the bicycle. It is like an astronaut in space who is overtaking a big
rock and kicks it in passing to get more speed, not like a ship ejecting mass
it is carrying in its own inertial frame.
The analysis can then be done in the frame of the rock, which is
similar to our analysis in the Earth frame, or in the initial frame of
the astronaut, which is similar to the analysis in the frame of the
buddy bicycle B.
As a temporary conclusion, there are also spaceships that use the "kick
in passing" technique to accelerate. They are still science-fiction,
but they have been seriously considered. They are the ramjet
spaceships, and work a bit like ramjet planes, with the same
constraints on minimal speed, but using space dust and gas instead of air as
accelerated reaction mass. The "more advance version", the Bussard
ramjet, is supposed to also collect energy from surrounding space, but
that is another story.
A: Both momentum AND velocity must be relative to the same thing. In other words if the two cyclists are going along at the same speed, the one cyclist's momentum relative to the other is zero. If they crashed into one another, both moving at the same speed, nothing would happen.
As for the formula, you can't say that $5KJ$ produces $10m/s$ and then another $5KJ$ $4.14 m/s$. The formula is not associative.
A: To answer your last question first - the energy depends on the square of the velocity, not the velocity itself. $$E \propto v^2$$ or $$v \propto \sqrt{E}$$
Which means when you double the velocity, you'd quadruple the energy input. For the example that you had given, to get a velocity of $20$ $m/s$ you'd have to give in an energy input of $20$ $kJ$. So clearly, when you double the energy input, you'll only see an increase in velocity proportional to $\sqrt 2$, and in your case that's $1.414 * 10 = 14.14$, which is exactly what you got. 
Hopefully this clears some of your confusion up. To answer your title question - As other answers have already pointed out, both momentum and velocity are relative. In special relativity, the momentum transforms as $$p = \gamma mv$$ where $v$ is the velocity of the body in one frame of reference, and $$\gamma = \frac{1}{\sqrt{1 - u^2/c^2}}$$ where $u$ is the relative velocity between the two frames of reference. So when one observer measures a different velocity because of his frame of reference, he will also measure a different kinetic energy.
A: Oke in order to understand this more intuitively lets calculate the following example.
We have 3 rockets of 100 kg side by side floating in space. Rocket 1 and rocket 2 have the same speed and rocket 3 has a speed $v_{int}$ different from rocket 1 and 2. whe call rocket 1 our observer and where gone try to get rocket 2 to they same speed as rocket 3
In space we cant talk about accelerating without burning some mass or/and switching to relativity. so in order to stay in the classical regime i will have to introduce the rocket equation $$ \Delta v = v_\text{e} \ln \frac {m_{init}} {m_{final}} $$ 
where $v_e$ is they effective speed of mass ejected.
And $\Delta v $ is the change in speed of the rocket.
And $m_{init}$,$m_{final}$ are the mass before and after the so called burn.
The velocity of the exhaust $V_e$ in the observer frame is related to the velocity of the exhaust in the rocket frame $v_e$ by (since exhaust velocity is in the negative direction)
$$V_e=V_{rocket}-v_e$$
now lets say rocket 2 has such a engine that if it ejects 1 kg of fuel ($\Delta m$) it will reach a speed $V$ equal to rocket 3.  so $$ \Delta v = V - 0 = v_e \ln\frac{100}{99}\approx0.01 v_e  $$
so our theoretical engine has a $v_e$ of a 100. Which tells us that there is a cloud of dust or fuel going the other direction with a speed of $100V$
now we check the kinetic energy used to reach that velocity.
$$ E_2 =  \frac{1}{2} \left[ m_{final} * V_{final}^2 + \Delta m*(V_e)^2\right]
\\=\frac{1}{2} \left[ 99 * V^2 + 1*(100V)^2\right] \\
= \frac{1}{2} \left[ 99 * V^2 + 10000*V)^2\right] \\
= \frac{1}{2} 100 99 * V^2$$
Where i have added the kinetic energy of the ejected mass plus the final rocket kinetic energy. You can clearly see that the amount of chemical energy converted in to kinetic energy is highly depended on your choose of $\Delta m$. So this is in space where we ejected a very tiny amount of our mass and the result is that we need a very large amount of energy (compared to our final kinetic energy) to reach our target speed.
But then why doesn't they ejecting mass matter for a bicycle? The reason for this is that on earth you ejecting mass is very very large. basically your ejecting they earth itself so $v_e$ becomes smaller and smaller the extra term $\Delta m v_e^2$ becomes smaller and smaller. this is due to the fact the  $v_e$ squares and $m$ is only linear.
so when you ask will it always produce 10m/s delta v they answer is it depends.
are you still propelling with the same mass ratio because that is they most important in rocket mechanics.   
A: Kinetic energy is frame-dependant. 
The reason is very simple: kinetic energy is the difference between Mc^2 (don't know how to write square here) and the rest energy M0c^2. M depends on v, which depends on the frame, so obv kinetic energy depends on the frame.
Note: I tried to give you a logical explanation other that E=1/2mv^2
