Well, velocity is in relation to a frame of reference. If we are talking groundspeed, then relative to the ground.
The magnitude of velocity is the rate of change of position-m/s, km/hr, furlongs/ fortnight- it is how much your positionn has changed in the reference frame and how long the change took. I don't see how that can have a negative value.