Conceptually, if you don't care about speed, take an algorithm that decomposes $N$-gons into $N-2$ "disjoint" (modulo common edges) triangles -- for convex polygons this is trivial -- and then, for each pair of triangles (one from $P1$ and one from $P2$), apply an algorithm that computes the overlap, if any, of two triangles.  This shows the complexity is at worst $O(mn)$, at least in the convex case.  One question might be, how does this compare with the approaches in the answers already given by meij and Stephen Sturgeon?