This is another achievement you will likely need to grind after completing the required campaigns. This one should come naturally without trying too much along the way to grinding 5000 kills. It really helps your total to go crazy destroying the level with the Gigantic Rocket power-up any time your get one. These have huge explosive power and can obliterate the entire level's blocks in a few shots.
You can check your progress towards 1.000.000 blocks upon completion of any level in the statistics screen.