The charts on the second link show the current and voltage needed to achieve different amounts of heating/cooling, but they say nothing about how long it takes to achieve that temperature change.
If the rate of change is high, then the possibility of overshoot is great. If the rate of change is low, then that is a lot less likely.
In either case, determining the appropriate on/off times would probably require the use of PID.
Is there any possibility of (at least initially) having a PC near the Arduino, to provide the graphic interface for setting/seeing temperature and cycle iteration and count?