It is true that mass doesn't increase except from the point of view of a second observor. But then, you aren't moving at all except relative to another observor. As far as you are concerned, you are always remaining motionless.
The formula that you have at the end of your post (I am assuming that it is correct -- I'm too lazy to look it up and verify it) is correct. Suppose that I am observing you move at a velocity equal to v1. Now in
your reference frame, you are motionless. Then you speed up to a velocity of v2. That means relative to your initial reference frame, your velocity is now v2; however
I watch you accelerate to a velocity of u, given by the equation.
How does this work? I am watching you accelerate. Let us say that you are in a vessel ejecting mass from a rocket; this is increasing your momentum by some amount, perhaps by a large amount. However, to get your velocity I must divide your momentum by your mass -- since your momentum increases a lot but your velocity doesn't increase by very much (after all there is no limit to how much momentum you can have, but your velocity is constrained by the speed of light) that must mean that your mass has increased by a large amount.
However, this increase in mass is just what I, in my reference frame, is measuring. To an observer in another reference frame, you will have a different mass. You, of course, being motionless in your own reference frame, see no change in your own mass.