How is it possible for the same force to do different amounts of work in two different inertial frames? Consider an object which has been given a speed $v$ on a rough horizontal surface. As time passes, the object covers a distance $l$ until it stops because of friction. Now,
Initial kinetic energy = $\frac{1}2mv^2$

And final kinetic energy is zero. Therefore, work done by friction on the object is equal in magnitude to $\frac{1}2mv^2$.

Now here is the part that I found weird: Consider another frame moving with a speed $v_0$ in the same direction with respect to the ground frame. Now, kinetic energy of the original object with respect to this new frame is $\frac{1}2m(v-v_0)^2$.
And, the final kinetic energy is equal to $\frac{1}2mv_0^2$.
So this means that the work done by frictional force, in this case, will have a magnitude of $\frac{1}2m[(v-v_0)^2-v_0^2]$, which is obviously different from the value which we get with respect to a stationary frame.And this part seems very unintuitive to me. How is it possible for the same force to do different amounts of work in two different inertial frames? (I would consider it unintuitive even if we consider non inertial frames, after considering pseudo forces).
And if we were to do more calculations based on the two values of the work done by friction, we would land on different values of some quantities which aren't supposed to be different in any frame. For example, the coefficient of friction would be different, as the amount of frictional force is constant, acting over a distance $l$. We can say that Work done by frictional force is $\alpha$$mgl$, where $\alpha$ is the coefficient of friction and $g$ is the acceleration due to gravity. We can clearly see that $\alpha$$mgl$ equals two different values.

So, is this just how physics works, or is there something wrong here?
 A: You have correctly discovered that power, work, and kinetic energy are all frame variant. This is well-known for centuries, but is always surprising to a student when they first discover it. For some reason, it is not part of a standard physics curriculum.
So, the reason that this is disturbing to every student who encounters it is that it seems irreconcilable with the conservation of energy. If the work done is different in different reference frames then how can energy be conserved in all frames?
The key is to recognize that the force doing work acts on two bodies. In this case the object and the horizontal surface. You must include both bodies to get a complete picture of the conservation of energy.
Consider the situation in your example from an arbitrary frame where the horizontal surface (hereafter the "ground") is moving at a velocity $u$, the ground frame then being the frame $u=0$. Let the ground have mass $M$. The initial kinetic energies are:
$$KE_{obj}(0)=\frac{1}{2}m (v+u)^2$$
$$KE_{gnd}(0)=\frac{1}{2} M u^2$$
Now, the friction force $-f$ acts on the object until $v_{obj}(t_f)=v_{gnd}(t_f)$. Solving for the time gives $$t_f=\frac{m M v}{(m+M) f}$$ and, by Newton's 3rd law, a force $f$ acts on the ground for the same time.
At $t_f$ the final kinetic energies are:
$$KE_{obj}(t_f)=\frac{1}{2} m \left(\frac{Mu+m(u+v)}{m+M} \right)^2$$
$$KE_{gnd}(t_f)=\frac{1}{2} M \left(\frac{Mu+m(u+v)}{m+M} \right)^2$$
so
$$\Delta KE_{obj}+\Delta KE_{gnd}=-\frac{m M v^2}{2(m+M)}$$
Note importantly that the total change in KE is independent of $u$, meaning that it is frame invariant. This is the amount of energy that is converted to heat at the interface. So even though the change in KE for the object itself is frame variant, when you also include the ground then you find that the total change in kinetic energy is frame invariant which allows energy to be conserved since the amount of heat generated is frame invariant.
A: The coefficient of friction is the same in both cases. You have assumed the distance traveled  to be the same in both cases, which is why you are getting different values for $\alpha$. Your other questions have been cleared in many answers above, so I just wanted to mention this point.
A: Calculating using the definition of work:
$W = \int_{x1}^{x2}{Fdx}$. For a frame moving at a velocity $v_0$, the change of variables are: $x' = x - v_0t$ and $dx' = dx - v_0dt$.
$W' = \int_{x1'}^{x2'}{F(dx - v_0dt)} = \int_{x1}^{x2}{Fdx - \int_{t1}^{t2}Fv_0dt}$
The first integral represents the work in the stationary frame. As mentioned in the other answers, the second one can be interpreted as the work done  on the second body (the "ground").  Theoretically, it should result on a decrease of its velocity, but as it is much more massive, there is a variable force and a constant velocity.
The first part can be used to calculate the kinetic energy variation for the stationary frame:
$\int_{x1}^{x2}{Fdx} = m\int_{x1}^{x2}{(dv/dt)dx} = m\int_{x1}^{x2}{dv(dx/dt)} = m\int_{v}^{0}{vdv} = -(1/2)mv^2$
But the second integral is: $\int_{t1}^{t2}{Fv_0dt} = mv_0\int_{t1}^{t2}{(dv/dt)dt} = mv_0\int_{v}^{0}{dv} = -mv_0v$
The work done, as measured by the moving frame is:
$-(1/2)mv^2 + v_0v$, matching your calculation.
A: Forces don't operate on only one object.  It's difficult to see, but the other object in the force pair here is the ground/earth.
In the frame where the ground is stationary, friction does no work on the earth, so we can discard the effects.  But in a frame where the ground is moving, friction does work on it as well.
In any frame, the sum of all work done is identical, but it may be distributed between the two objects in different amounts.  Perhaps in the earth stationary frame the net result is the object loses 50J and 50J of heat is produced.  In a different frame you might find the object loses 250J, the earth gains 200J, and 50J of heat is produced.
A: In theory of motion: given the relativity of inertial motion the way to look for understanding mechanics taking place is to look for an invariant. Here 'invariant' refers to a representation that is independent of the choice of the origin of the inertial coordinate system.
Here are the things I need to put in place for that:
In the case of two masses $m_1$ and $m_2$ we can state the velocity of each mass as a velocity with respect to the Common Center of Mass (CCM) of the two masses
$m_1$ Mass of object 1
$m_2$ Mass of object 2
$v_1$ Velocity of object 1 relative to the CCM
$v_2$ Velocity of object 2 relative to the CCM
$V_r$ relative velocity between the two objects
$V_c$ velocity of the CCM relative to some chosen origin
$$ v_1 = V_r \frac{m_2}{m_1 + m_2}  \qquad (1) $$
$$ v_2 = - V_r \frac{m_1}{m_1 + m_2}  \qquad (2) $$
This notation embodies that with respect to the CCM the total momentum of a two particle system is zero: $m_1v_1 + m_2v_2 = 0$
The total kinetic energy expressed in terms of  $v_1$ and $v_2$:
$$ E_k = \tfrac{1}{2}m_1v_1^2  +  \tfrac{1}{2}m_2v_2^2  \qquad (3) $$
Using (1) and (2) to change (3) into and expression in $V_r$ and $V_c$:
$$ E_k = \frac{1}{2} m_1 \left( V_c + V_r  \frac{m_2}{m_1 + m_2} \right)^2 + \frac{1}{2}m_2 \left( V_c - V_r  \frac{m_1}{m_1 + m_2} \right)^2  \qquad (4) $$
A lot of terms drop away against each other, and the expression can be separated in a component in terms of the velocity of the CCM with respect to some chosen origin, and the relative velocity between $m_1$ and $m_2$
$$ \begin{align} E_k & = \frac{1}{2}(m_1 + m_2) {V_c}^2 + \frac{1}{2}\frac{m_1{m_2}^2 + m_2{m_1}^2}{(m_1 + m_2)^2} {V_r}^2 \\       & = \frac{1}{2}(m_1 + m_2) V_c^2 + \frac{1}{2}\frac{m_1m_2}{m_1 + m_2} V_r^2 \\\end{align} $$
Of course, we can make the $V_c$ term zero by choosing a coordinate system that is co-moving with the CCM. Then the expression for the kinetic energy is:
$$ E_k = \frac{1}{2}\frac{m_1m_2}{m_1 + m_2} V_r^2 $$
What this illustrates is that there is no such thing as the kinetic energy of a single object. Kinetic energy is meaningful only in terms of the relative velocity between two objects.
It's just that when the other object is far, far more massive there is negligable error in simplifying the expression to:
$$ E_k = \tfrac{1}{2}m_1V_r^2 $$
