En un teléfono Android, si tienes, digamos, 32GB de almacenamiento interno, eso no son 32GB de espacio para usar. El espacio está particionado, al igual que un ordenador con un solo disco duro tiene una "unidad C" y una "unidad D" - ambos son la misma unidad, pero está particionada en 2 piezas.
La mayoría de los teléfonos Android están particionados en al menos 5 o 6 piezas, algunos mucho más. Así que el espacio que tienes que usar no es de 32GB, podría ser tan poco como 1 o 2GB.
Instala una aplicación de terminal y emite el siguiente comando:
df
(Es más fácil leer los resultados en modo apaisado.) La última línea debería estar etiquetada como emulated/0, userdata o sdcard (no es la tarjeta SD, es una partición llamada sdcard). Esa línea muestra el tamaño total de esa partición, la cantidad usada y la cantidad libre. (Los títulos de las columnas están en la parte superior de las mismas). El tamaño en esa última línea es todo lo que está asignado para su uso. (Y si recibes una actualización que es más grande, puede reparticionar el almacenamiento y dejarte menos.)
Así que si ves que sólo tienes unos pocos MB libres, es porque el almacenamiento está lleno - no tenías mucho para empezar.