Cells self-organize into functional, ordered structures during tissue morphogenesis, a process that is evocative of colloidal self-assembly into engineered soft materials. Understanding how intercellular mechanical interactions may drive the formation of ordered and functional multicellular structures is important in developmental biology and tissue engineering. Here, by combining an agent-based model for contractile cells on elastic substrates with endothelial cell culture experiments, we show that substrate deformation-mediated mechanical interactions between cells can cluster and align them into branched networks. Motivated by the structure and function of vasculogenic networks, we predict how measures of network connectivity like percolation probability and fractal dimension as well as local morphological features including junctions, branches, and rings depend on cell contractility and density and on substrate elastic properties including stiffness and compressibility. We predict and confirm with experiments that cell network formation is substrate stiffness dependent, being optimal at intermediate stiffness. We also show the agreement between experimental data and predicted cell cluster types by mapping a combined phase diagram in cell density substrate stiffness. Overall, we show that long-range, mechanical interactions provide an optimal and general strategy for multicellular self-organization, leading to more robust and efficient realizations of space-spanning networks than through just local intercellular interactions.