Follow up on Ben's idea:
Take n as an optional argument, init value #f.
On first application of f on the first values, continue n-map with n=received number of values. Once arrived at the empty lists you know how many values you should have.
At each iteration, you can even check that the number of values doesn't change (or take the max?).
The only corner case is when provided with empty lists from the start, in which case either the user can specify the init value for n if it is known, or you can throw an exception.