Try to uninstall updates for Google Play services.
Go to Settings -> Apps -> Google Play services -> click 3 dots in upper left corner and select "Uninstall updates".
After some time phone finds update for Play service. Install it.
I managed to resolve in the end, turns out my SD card was corrupted even though it wasnt telling me that. only after factory resetting my phone i realised this was the case.