I would suggest that the problem lies in the speed you are trying to do this. Cutting a thread - e.g. an 8 mm thread - this is 1.25mm pitch. That is 10mm movement for every 8 revs of the spindle. If you can move your axis at 500 mm per min, this means a spindle rev of only 400 revs per min. This is slow for the average 3 phase motor on an inverter, and you will loose power.

Really you need to be in the equivelant of backgear on the lathe to get the spindle speed down to these low speeds, but still retain the power of the reduction gearing to maintain a smooth cut. You need to have everything working well with parameters to do a nice thread.

On the old lathes, with thread cutting gearing, they were usually cut in backgear.

You will have to ask someone who has more experience of threading ( Hood might be able to answer) - but the answer MUST be YES.

Quite clearly the speed of the Z axis must be varied with the speed of the spindle.

When you say the Z travel does not seem to vary when you alter the spindle speed - are you doing this on the "fly". If so, the only thing I can think of is Mach looks at the "line" of Code and says  - I am going from A to B, pitch is X, spindle speed is Y therefore my Z speed is whatever. It then puts out that information until the move is finished - and does not vary the speed whilst moving.

This is why I am saying that the machine should be working well within its parameters, so there is little likelyhood of anything altering.
The best way is perhaps a set of gears connecting the spindle to the lead-screw (now where's my spares box - I have some somewhere)

To be honest I am not sure, will be a hard thing to test on my Lathe as the speed is set by clutches and so is not variable within the speed ranges. I couldnt take a test cut deep enough to slow my motor down either, the tool would break long before the spindle would slow. I have taken 12mm DOC (1 inch on Dia) on a 3inch Dia EN24 bar and the motor hardly changed sound so there is no way a threading tool could slow it.
 I would imagine that Mach steps are put out per revolution and maybe as Graham said if the timing pulse and a multi slotted disc is used it will be less than a  rev but I just dont know for sure. I may be able to test it out on the mill as that has a pot to control the spindle via VFD, just have to remember to try it out and see LOL
Hood

MACH software does NOT allow for electronic gearing of the z to the spindle. SO no mach cannot alter the z feed to compensate for spindle speed variations while in cycle. It monitors the RPM and sets the feed to the RPM at the start of the cycle. IF the RPM varies too much then the threads suffer accordingly.

HOPE that helps, (;-) TP