Right, this is so straightforward it is embarrassing. The key was to group by the two map keys that I wanted to keep, and there's a handy groupCount() to make it even easier. Like this:
g.V().hasLabel('city').
out('hasParking').
out('hasSlot').
inE('parkedAt').has('time', P.lte(2)).has('time', P.gte(1)).
project('city', 'parking', 'vehicle').
by(inV().in('hasSlot').in('hasParking').values('name')).
by(inV().in('hasSlot').values('name')).
by(outV().values('name')).
dedup().
groupCount().
by(select('city', 'parking')).
unfold()