In this paper we address the problem of registering and merging two maps in two dimensions, given covariance estimates of the two maps. We show that if two maps are given in the same coordinate system, then the problem of merging them in a statistically optimal way can be formulated as a linear least squares problem, but if they are given in different coordinate systems as well the problem becomes highly non-linear and nonconvex. We show how we can relax the problem slightly in order to optimize over the registration (i.e. putting the two maps in the same coordinate system) and at the same time optimize over the merged map. The approach is based on finding all stationary points of the optimization problem and evaluating these to choose the global optimum. We show on synthetic data that in many cases the proposed approach gives better results than naively registering and merging the maps. We also show results on real data, where we merge maps given by time-of-arrival measurements, and in these cases simpler linear methods perform just a good as the proposed method.