Apparently this is due to a hardware issue with the Flash memory (not that that excuses the slow performance!).

You can still go back to Kitkat by resetting it (I did and the performance difference is astonishing).