I think it all becomes obvious when you realize that for much of the time both people will be simultaneously walking different parts of the route.
This is analogous to multi-core computers completing a task faster than a single one could when it is possible to split the task up into chunks and process them in parallel.
Exactly. The journey is over when the last person gets to the end. That person basically alternated riding and walking, say average 50-50. So assume walking 3mph and cycling 12mph and it takes 1/2 + (1/2)x(3/12)= 5/8 of normal walking time.
Your mileage may vary.
Now what happens if there are 2 bikes and 3 people? 
It is true that someone is always walking. However, when everyone has stopped walking, less time has elapsed that would have elapsed if there had been no bike.
A better argument would be “every inch of the distance was traveled by someone on foot”.
To counter the latter argument you’d note that without the bike the whole distance would be traveled by two sets of feet. The bike allows you to reduce that to one pair of feet per inch and for the two people to walk simultaneously, covering different stretches of the distance. To see that more simply, imagine two highway line painters: instead of walking 2 miles together for an hour painting a double line, one starts at the half-way point and in half and hour their two separate lines join into one, 2-mile long line.