Most missions have around 35 levels each of which is around 150x150 which adds up to roughly 870,000 blocks per mission. I would recommend going for it after completing all other achievements in a completed level by strip-mining the entire level starting from the top.
Note that the achievement tracker doesn't update until you save and exit a level and trying to load a mostly-mined level can cause the game to crash. Therefore, I would recommend either mining the whole thing in one go, or loading up a different level if you didn't get the achievement after saving and exiting.