With the paid version of Avast Cleanup, I would have thought that you would be able to access its settings to either set your default search engine (something should also be in your browser relating to that).
Possibly more crucial, is this happening after a scan or only when you search ?
I don't use avast cleanup, so I can't speak from personal experience, but I would have thought it could be set to only run when you run a scan.
My other concern is why this action is on the browser search engine and that is the component that I would expect to be looking after your browser, not the avast cleanup component (paid or free). Are there any settings in the paid avast cleanup that would allow you to disable the search engine check ?