How to subdivide a mesh where it intersects another mesh
One way is to use the Knife Project tool. 


Make the arches one object and the square a separate one.
If necessary, scale up the arches so they are definitely crossing the border of the square object
In object mode, shift select the arches object and then the square object
Tab into edit mode (you should now be in edit mode for the square)
From the toolbar (T) choose Knife Project. The arches will be projected onto the square, sometimes creating n-gons (although by the appearance it looks like the objects have just been merged, the faces have in fact been subdivided)
You can now delete the original arches mesh in object mode.




Alternatively, another way you could do it would be to remove all but 2 sides of the original square resulting in 3 sets of edges, the edges of the square and the two arches:



With the arches and the square as a single object select them all and then press W> Bridge Edge Loops:



Both methods require some form of clean up afterwards, the bridge edges method needing slightly less. With the bridge method the clean up will also be less if the number of vertices in the arches are the same as the number of vertices in the square's sides.