When it involves a compromise that cannot be fixed by a typical, consumer anti-virus/anti-malware app nor wiped away by a Factory Reset, it's now a matter where you have to reinstall the Android operating system. With the Android platform, it's a process referred to as 'flashing a ROM'. Flashing is the process, a ROM is the firmware package, the actual operating system software and system files, that gets written to your phone's internal storage. It's typically not a difficult thing to do but it is quite involved and very, very specific -- you can do it yourself if you're good at following directions and paying attention to details, but if you're not comfortable doing such things (most people are not) than you'll need to have this done at a trusted, phone service center.
Since you didn't list just what phone you have or what version of Android it's running, it's not possible to be more specific so you'll need to find what you need to do by just doing online searches yourself. Different manufacturers require different ways to do the flashing, so if you have a Samsung device it will require using the Odin utility, but keep in mind Odin won't work on flashing to a Moto device. (Moto phones rely upon the blandly named 'Flash Tool' utility). It's also vital you use only the ROM that's specific to your device model. ROMs are not interchangeable, and this can't be stressed enough. Be sure to only use the stock ROM that corresponds directly to your device model. Don't mix and match on a whim. Most download sites for ROMs will include instructions on the flashing process required.
Just for background, there's a reason why this is required and it's a very conditional matter.
-- The internal storage in your Android device is divided into several partitions. Most of these partitions are dedicated to the operating system and are protected by system-level permissions to the file system. One partition is set aside as the user data partition, and it's not limited by any system-level restrictions. The Android operating system resides within those protected system partitions, while your files and data get stored in that user data partition.
So there's an important aspect to keep in mind, you (the user) only have full, unfettered access to the files and folder stored within that user data partition but you only have very limited access to anything stored in those system partitions.
-- When you install one of those anti-virus/anti-malware apps from the Play Store, they're being installed as just user apps. That's a really important point. Being just user-installed apps, they only have user-level permissions so while being effective on all the files and folders within a user data partition, they have very little to no ability to anything to data stored within a system partition. Most Android malware only affect user data so they're often readily fixable/removable, but there are a few isolated exploits that are able to infect the installed operating system. They're more professionally-crafted and insidious, and harder to detect to and to fix or remove. And that's why those consumer level utilities can't fix your problem -- an A/V app with only user-level permission status can't fix anything with system-level permissions.
-- A Factory Reset is a bit of a misnomer. A FR only does one thing, it wipes the user data partition clean. It does not remove everything (installed Android OS and user data), it only removes the user data. If it did wipe the OS, that would brick the device -- with no existing firmware you'd have a device that can't even start up, the display would just blink and that's about it. And no, a Factory Reset does not magically reinstall the existing Android OS -- the same operating system that was running on your device before doing a Factory Reset is the same as after. So in your case, if there is some exploit installed in the operating system itself, this is why a typical app nor a FR will solve the problem. Restoring a new, clean operating system requires you to manually do that flashing process.