I'd be surprised to see more than a couple minutes for even a complicated fax page. I've seen 45-70 seconds average for a not-too-complicated page.
It also depends on the baud rate (never thought that term would come back, eh?) negotiated between both ends. A 14400 baud transmission will of course be faster than 9600.