It's not about turning the screw right or left, which, as you say, is a meaningless concept, since the screw does not move to the left or right but just rotates.
It's all about using the right hand or using the left hand to turn the screw.
If you clench your fists and put your hands in front of you, thumbs upwards (it's very hard and almost impossible to do it any other way - try it), and twist your right hand so that your thumb moves away from your body (a natural movement), then you are tightening up the screw (clockwise). If you make a similar movement with your left hand (move the thumb away from your body towards the left), then you are loosening the screw (anticlockwise).
This, it seems to me, must be the origin of the terms right-handed screw and left-handed screw.