Rather than removing the blocks, I think dig-dug actually drew the tunnels over the dirt textures.
Would save you from drawing thousands of tiles, Just make your dirt in one layer, and have your player and ready made tunnels in another layer so it draws on top of the dirt.
When the player moves off a tunnel tile have it draw another tunnel tile in the direction the player is facing.Then you will have a digging effect, and you wont need as many collision sensors. Just have the collision sensor on the player and monsters to make sure they are on the tunnel tiles. When the monsters are over the diet tiles either have them draw more tunnels in front of them (dig), or turn into the "ghost eyes" as they are floating under the dirt like the arcade game.
TL;DR, paint tunnels OVER the dirt, do not remove the dirt...
Hope that makes sense :D