Which web browser are you using on your phone? you really should investigate your default search engine on whatever browser you are using same for your extensions / addons depending on which browser you are using.
In any case you should really backup then factory restore your phone, be sure to not allow the phone to re install all of your apps once you start signing into your accounts. . You may very well have a malicious app installed on your phone for example.
Do the popups happen randomly or when searching for something on the web?