Making changes to the root category (confusingly not the one that is flagged "is_root_category" as that's actually the "home" category) sounds scary but the actual category changes were fine and the structure hasn't changed since 1.6. I'm now questioning whether the categories caused this at all.
I'm beginning to think that the issue might actually be down to the collations in the database (I think that they should be utf8mb4_general_ci but not all of them are). Basically I'm thinking there's a size mismatch in the serialized data but I am indeed exploring the data itself it to see if there are any clues....
Thank you for the heads up on the Prestools - I'd never heard of it before but it looks like it could be useful!
UPDATE: Prestools integrity check didn't find any issues (and under the category menu displayed the category tree correctly and completely) so am guessing the category fixes were a red herring and the profiler issue is something completely separate. All 124 categories are present and correct. Have changed the collation off the tables to utf8mb4_general_ci too, just in case but no luck yet.