The Arduino is perfectly capable of reading the encoders and computing the speed that the carriage is moving. From this, and the stitch length desired, you could compute how fast the needle needs to move up and down. From that, the motor RPM needed to move the needle at that speed can be computed.
The hard part, then, is driving the AC motor on the sewing machine at the correct speed.
A google search for AC Motor Speed Controller turns up a number of low cost options.
The encoders that the stitch regulator in your link uses are not cheap. They work pretty well, though.
My wife has a similar unit, and it works quite well. Keep us posted on how your project goes.