I had to do it on my Nexus 7 with the lollipop update, and it is not uncommon however much it sucks, but...
You may want to do a factory reset with the update and do a do-over. Not all upgrades happen smoothly, and the performance problem in particular you note is something I have seen before with system upgrades across versions. Usually point upgrades (4.1-4.2 for example) work pretty reliably. But major releases, like 4 to 5 like you just had done, do not always work right. I am running lollipop fresh on my m8 and its running great, so I doubt it is the software itself, but likely the upgrade process. A reset+do-over will probably get you running, though with the work required to do so of course.