I did a test backup with only 2 mailboxes from the IT department since I know some of them contains some meat.
Here are the stats:
First full backup:
xxxx.onmicrosoft.com; 2016-10-19 15:55; 19 minutes, 26 seconds; Items: 37866 (1,59 GB); Processing rate: 32 items/s (1,40 MB/s)
Incremental 8 hours later:
xxxx.onmicrosoft.com; 2016-10-20 00:01; 1 minute, 40 seconds; Items: 16 (642,66 KB); Processing rate: 0 items/s (6,39 KB/s)
Please let me know if I can run more test jobs.
Btw just for kicks I did
(Get-Mailbox -ResultSize Unlimited).Count
I did not measure it accurately but I believe it took about 10-15 minutes. So the issue with listing mailboxes at large tenants is probably a limit with Office 365. This would make it even more interesting to get the ability to filter on properties.