Problemas con malware y virus

Hola gente, vengo en busca de ayuda. Hace un tiempo instalé un link desde internet creyendo que era una app. Por apresurarme, no me dí cuenta de que acababa de instalar un virus y comenzó a hacer de las suyas. Daré datos
Modelo: SM-G531h (galaxy grand prime), android 5.1
Esta molestia es típica; aquel malware que instala apps sin permiso. Busqué y rebusqué la carpeta y la encontré, porque son letras y números random.
Me instala apps basura como Beacon flashlight, todas las cosas de Claro apps (shop, música, películas), tonos y fondos, conterstone, transfer, noticias águila, y hasta aplicaciones de Telcel (Promo amigo y Mi telcel). Si las desinstalo, se vuelven a instalar después de unas horas
He intentado de todo y nada me funciona. Fui a un local a asesorarme y me dijeron que la única solución es quitarle este software y ponerle otro nuevo... obviamente ya no sería el original. Y sinceramente no quiero hacer eso.
Quisiera que me dijeran cómo solucionarlo. Ya soy usuario root. Quisiera eliminar esa carpeta para siempre.
La carpeta cambia de nombres:
Z0tPWGhhQi8za0tVWWxBUmo1NzAxM2JIYxE1, Z3FhWFJmQiszVWZVVWdBQWIaNzAxODc2Yjg1
De antemano agradezco su ayuda, los leo con atención.