FWIW this is what Rakudo currently does, and I believe it is correct:

1zz     -> 2aa
zzz     -> aaaa
zz1     -> zz2
z1z     -> z2a
zz9     -> aaa0
Z9Z     -> AA0A
[download]

It always starts at the last character, auto-increments that, and if there's an overflow it auto-increments the character to the left, recursively.

It has the additional magic of stopping at a dot, so img001.jpg auto-incremented becomes img002.jpg.