I think in this case it is necessary to do a closer examination of the concept of kinetic energy.
Kinetic energy attributed to an object is kinetic energy with respect to some specified coordinate system.
The kinetic energy attributed to an object is the amount of work that must be done to bring the object to a standstill.
Let's say we have an object, moving at velocity, and the object is slowed down by ribbons that are positioned perpendicular to the direction of velocity. (Think of the type of ribbon at the finish line of a running event.) The ribbons stretch, and then snap.
For the sake of the thought demonstration we treat the ribbons in a highly idealized way. We treat the mass of the ribbons as negligable, so that only the elasticity of the ribbons changes the velocity of the object. Just as each ribbon snaps the next ribbon is touched so that the decelerating force is effectively constant, resulting in uniform deceleration. Let the ribbons be spaced one meter apart.
To make the numbers simple we use a deceleration of 2 $m/s^2$. If the object comes in with a velocity of 4 m/s then it takes 2 seconds to come to a standstill, and over the course of those 2 seconds 4 ribbons will be snapped.
If the object comes in with double that velocity, 8 meters per second, then the total duration until standstill will be double too: 4 seconds. On the other hand: the amount of ribbons snapped will be quadrupled: 16 snapped ribbons.
Also: in the first half of the time 3/4th of the total number of snapped ribbons is snapped, in the second half of the time the remaining 1/4 of the total number of snapped ribbons is snapped.
Acceleration/deceleration is the second derivative of position, that is what gives rise to that quadratic relation between coming to a standstill and distance traveled.
To your question about frame A and frame B:
For the object to come to a standstill with respect to frame A requires a certain deceleration distance, and to come to a standstill with respect to frame B requires a certain deceleation distance, and those two distances are not the same.
Incidentally, I think the following is another way of casting the apparant paradox that you describe:
Take a train of flatbed cargo wagons, with connecting ramps such that a car can travel over the train of cargo wagons, as if travelling over a road.
Bring the train to, say, 4 m/s velocity. So: work is done, giving the car kinetic energy relative to the ground. Then start giving the car a velocity with respect to the train, accelerating to 4 m/s. So: work is done giving the car kinetic energy relative to the train.
That car will run out of train, and will hit the ground. the kinetic energy relative to the ground is not the sum of the two kinetic energies mentioned above. Instead it's the kinetic energy of a relative velocity of 8 m/s