No. of instances of design, is just a single parameter to represent the complexity of the design.
Please provide other details like the area, frequency, power domains & methodologies, etc. you are suppose to use.
Anyway, as per my knowledge all these three tools (ICC, SOCE & Magma) have the capability to handle a design of 3.6 million instances.
It mainly depends, with which tool you are comfortable.
Generally in big vlsi companies, they have there own flow with several scripts & wrappers to harness the tool's capability as per their need.
For an example:
I just completed a fullchip project of 45nm technology, having about 20 million gate count. And we used Magma for floorplanning, powerplanning, routing. For backend checks, we used Hercules, Celtic, PTSI with few more internal tools.
And it was really a very big design with almost all low power methodologies.
All i want to say may be as per the requirement you have to use other tools in conjunction with any of those three.
Hopes this information will be helpful for you.