I've started to dig out and play with some older devices that have been laying around and got to my Android tablet and remembered why I'd not bothered charging it up in ages. When I bought the Asus Nexus 7 it was really quick and worked great, but when I upgraded it to Android 5.1.1 it slowed down to a point where I gave up trying to use it.
When I charged it up yesterday I got so hacked off with it running slow that I went off to Google for the answer. And would you believe it. There it was right in front of me.
You have to restart the device into recovery mode
Then you select to wipe the cache partition
Restart the device and it all works great
So it turns out that when you upgrade Android it leaves a bunch of old files in the cache partition and doesn't clean them out.
I followed this post, but your mileage may vary.