1) ShapeMerge fails:
From my observations in 2019.1 ShapeMerge fails if the shape size exceeds the border of the mesh. If this was possible before, it`s an regression and should be reported as bug.
2) Boolean performance:
I did some tests with a 500k poly plane, and while it took some time to process, performance wasn`t nearly as bad as your findings. But since i don`t know how complex your scene is, i take my findings with a grain of salt. ProBoolean failed completely on the task,btw. I think you could perhaps streamline the process a bit by keeping the Boolean compound and successively clicking the objects you want to substract.
3) Known issues: There is an performance regression with polymeshes in 2019.1 that you can read about in the release notes. If this is related somehow with your issues i can`t tell.
There`s not much i can suggest here: Perhaps try to layout your streetplan entirely with shapes using the new ShapeBoolean and THEN use ShapeMerge once to cut out from the plane.Might work. Just make sure the shape is within the boders of the plane mesh.
Perhaps @hagen.deloss can give us more insight on what`s going on with meshes in 3dsmax lately.
