HTC One internal storage performing very slowly
Resetting my phone did the trick.

This isn't a very good answer, as I don't know the root cause. I'm going to slowly add back apps and see if there's a particular one that might have been a bit IO greedy. So far I've added most back and its still fantastically fast again. Haven't signed into Facebook yet... I've always had my suspicions...