I have a Samsung S6. When using Google the app will lock up, then a message appears asking if I want to close, wait, or give feedback. I close it and reopen it, same thing in a few minutes every time. I got rid of old info to free up space. Right now it shows 1.7/3 GB of memory, 16.8/32 GB of storage. I went to Mygoogle activity, deleted everything for "all time", all the Youtube items, all of it. I even checked it through the web app by clicking the three dots, browsing history, delete for all time. It all shows clear. Start cruising the web again, it freezes, gives the same message and closes. The strange part is even after clearing before the crash, closing and re-opening to verify the history is clear, then start browsing till it crashes again I notice that after re-opening right after the crash, all the history has returned, some of which are places I have not been to in months. I downloaded Malwarebytes, did a scan, got a clean bill of health. WTF.
This sounds like a case of using a machine gun to kill an ant... when only a can of raid will do.
In other words... Itis not necessary to delete ALL of your activity on Google.com... just to fix a problem with an app, on your phone. The error message you keep seeing is called an App Not Responding Dialogue (ANR, for short), & the way to get rid of it is as follows:
1. Go to the Google Play Store (Different app, on your phone, looks like a multi-colour arrow.)
2. Hit the three horizontal slash marks, in the upper-left corner of the app, and this will take you to the Menu.
3. Under "My Installed Apps", look for the one that says simply "Google".
4. To the right of that, should say "Update" (If you don't already have the latest version of the app); Hit it.
5. Wait... for...it... to finish downloading... and installing. Once finished, it should say "Open"; OPEN IT
If that doesn't stop the ANRs, than go to your "Settings" app (Should look like a gear symbol), look under "Apps/ Applications".
Scroll down ⬇ to the Google App, look for an option called "Storage"; Hit it.
Somewhere, at the top, it should say "Cache/ Clear Cache".
Every online help article used the old "your memory is full" diagnosis so I tried it. I followed both steps you outlined. It works for a little longer, but still crashes. Maybe go for grenades over the machine gun now? I did try a nuclear football approach. While at the download site I noticed an add for "Duck Duck go" . So I went back and downloaded that. It works like a dream with no problems. I don't miss the advertising driven google search so I am thinking I will keep using this. I can even still use googlemap through it and I love the little flame icon they have to clear tabs and data. I am not fond of all the tracking done on the web to specifically try and sell me something.