Only option that could actually remove the Malware from your device is performing a Hard Reset on it. No Antivirus, whether paid or free, is going to solve this problem, except Formatting it, so back up your data and format it.
Mind you an antivirus will only add to your issues. They do everything apart from safeguarding your device from potential malware. Read here, why antiviruses for android are no good. (link removed by moderator)
The best way indeed is to create a backup of your valuable data and format the device.
If you think you have malware on your phone, it’s important to stop the malware from causing any further damage. Here are a few steps you can take.
1) Power off the phone and reboot in safe mode. Press the power button to access the Power Off options. Most Android phones come with the option to restart in Safe Mode. Here’s how, according to Google, although Safe Mode can vary by phone: Press your phone’s power button. When the animation starts, press and hold your phone’s volume down button. Hold it until the animation ends and your phone restarts. You’ll see “Safe mode” at the bottom of your screen.
2) Uninstall the suspicious app. Find the app in Settings and uninstall or force close it. This may not completely remove the malware, but it could prevent further damage to your device, or from it transmitting the malware to other devices on your network.
3) Look for other apps you think may be infected. There’s a chance that some apps may have been infected by the malware. If you think you can identify those apps, delete them immediately.
4) Install a robust mobile security app on your phone.
Remove an Android malware virus put your device in Safe mode, if necessary remove its administrator status and then uninstall the affected app Android viruses are delivered via apps installed on your device, so if your phone doesn’t already have a virus, the best way to avoid it getting one is to never install software outside of the Google Play app store.