Membership testing in transformation monoids
The nondeterministic polynomial-space algorithm for this problem works as follows:


Initialize h: A→A to the identity mapping.
Is h=g?  If so, we found out that g is in the monoid generated by S; accept and halt.
Guess one element f∈S.
Update h to f∘h.
Go to step 2.


As you correctly pointed out, the sequence can be exponentially long in the input size, so this algorithm may take exponential time before accepting.

Note that the algorithm does not guess a whole sequence at once and store this sequence in the work space—doing so would require exponential space.