I think that settles it. I was already considering this before, but now I'm actually going to do it. Before crossing the border, I'm rooting my phone so I can take a full disk image, which I'll leave at home. Then I'll factory reset and just load what I need for the trip^. It's a pain, but worth it to avoid the chance of this kind of invasion of privacy.

^Can make an image of that too for ease of use on future trips.

Of course, if they can do this, there's nothing really stopping them from forcing you to log into your webmail either, so maybe there's nothing you can ultimately do. (At least short of creating elaborate decoy accounts, but then you're actively lying to them, which probably isn't a great idea.)