Another possibility is that an update to one of your apps has started this. Basically anything you installed or updated shortly before this started is a suspect. The "Peel Smart Remote" thing Mike mentioned was one example of that: an app that had been around for years became an aggressive ad-pusher after an update. If you've anything from DU, Go, CM, ES those might also be possibles. With really aggressive adware stuff installed from outside the Play Store is more likely, but Play Store apps can't be assumed to be free of it.
Actual malware is unlikely from the Play Store (though that statement varies with country - at least a year or two back the Russian Play Store was a lot less safe than the UK one). Being released with Android 6 reduces the risk of a rootkit malware at least (which would not be fixable with a factory reset), since those generally rely on vulnerabilities of earlier Android versions.
