How to union many polygons efficiently

Likely the best method is to perform a simultaneous plane sweep of all the polygons. This is discussed in The Algorithms Design Manual under "Intersection Detection." (Algorithms to find the intersection can be altered to instead find the union.) It is also discussed in my textbook Computational Geometry in C, Chapter 7, "Intersection of NonConvex Polygons." The time complexity is $O(n \log n + k)$ for $n$ total vertices and $k$ intersection points between edges of different polygons.

Martin Davis describes an approach on his blog which he calls "Cascading Union".

The approach is to traverse a spatial index like an R-tree, to union polygons that are likely to overlap or touch, which gets rid of a lot of internal vertices. The naive approach might not reduce the number of vertices at all between two iterations...

Martin Davis description (snippet):

This can be thought of as a post-order traversal of a tree, where the union is performed at each interior node. If the tree structure is determined by the spatial proximity of the input polygons, and there is overlap or adjacency in the input dataset, this algorithm can be quite efficient. This is because union operations higher in the tree are faster, since linework is "merged away" from the lower levels.

Complexity

I don't know the exact complexity of the algorithm, but could be similar to the sweep line algorithm, since the complexity of the algorithms depends on the number of vertices remaining in each step.

See also the full description of the Cascading Union algorithm on Martin Davis blog.

If the polygons either share exactly one edge or are disjoint then create a list of edges and the polygons they belong to and then remove each edge that has two polygons, joining those two polygons.