That one mole of $\ce{CaCl2}$ is more effective in melting ice than one mole of $\ce{NaCl}$ is explained by the van 't Hoff factor. The freezing point depression of a solution is calculated by
$$\Delta T=K_fbi$$
where $K_f$ is a cryogenic constant which is specific to the solvent, $b$ is the molal concentration of the solute, and $i$ is the van 't Hoff factor, which indicates number of solute particles. In this case, it is the number of ions produced upon dissociation. Because $K_f$ and $b$ are constant, and $i=3$ for $\ce{CaCl2 \rightarrow Ca^2+ + 2 Cl-}$ and $i = 2$ for $\ce{NaCl \rightarrow Na+ + Cl-}$ the freezing point depression is greater for $\ce{CaCl2}$.

The reason $\ce{CaCl2}$ is widely used as melting agent may have more to do with keeping the concrete intact. Concrete is composed of many calcium-containing species. When water flows over the concrete, the calcium can be leeched out, and the concrete becomes brittle. The higher the calcium content in the water, the less leeching occurs, and the concrete remains structurally sound.