ESI & MALDI Mass Spectrometry: particle mass vs. measurement error
The answer to your question is not an easy one, as multiple parameters need to be taken into account to give an answer. At the high masses that you quote, most of the litterature trends come to their limits in terms of extrapolation, as the major mass ranges in mass spectrometry covers an $m/z$ range 10 - 4 000.

As you indicate in your question, one should separate the question into two parts: how does mass accuracy change with high $m/z$ values and how does mass accuracy change with high mass values, considering a high number of charges, as can be achieved in ESI.

Dependence with ion charges

I will first tackle the second part of the question, because this will be needed to answer the first part. If one considers a mass analyzer in which measurement accuracy ($\Delta m/z$) is directly proportional to the measured $m/z$ result, we have: 

$$\frac{\Delta m/z}{m/z} = Constant = \frac{\Delta m}{m}$$

Therefore for such a mass analyzer there is no direct advantage in using multiply charged ions (as produced in ESI) compared to singly charged ions as produced in MALDI. From this point, it comes that on this criterium alone, one should consider if measurement accuracy increases faster or slower than a proportional increase to decide whether multiply charged ions come as an advantage or a disadvantage.

Dependence with mass analyzers

Let us now consider a series of classic mass analyzers and consider how they would perform in terms of high mass measurement. 

Quadrupole filters and quadrupole ion traps

I group these in the same subtopic, as when one is concerned about high masses they have fairly similar properties. Commercial instruments are usually limited to $m/z$ 4,000 (or 32,000 for the specially devised systems). So ESI is a requirement for high mass species.

Quadrupole mass filters are usually operated in the constant mass width mode ($\Delta m/z = C$, with $C$ on the order of 0.5 to 1.3 amu), which means that the mass error will be roughly only dependent on $z$ and that there is an advantage to work on the high end of the $m/z$ range, as the overall error will be lower than on the low end. One point worth notice though: if you consider a 2 MDa system at $m/z$ 1,000, it would mean $z = 2000$. Thus spacing between neighbouring charge states is of only 0.5, lower than quadrupole resolution, which means that a deconvolution of the charge state distribution will not be doable and that is will be globally not possible to determine the mass of the molecule with this technique.

Time-of-flight analyzers

These are probably the mostly used analyzers for high mass compounds, both in MALDI and ESI modes. In an ideal TOF, the mass accuracy would depend only on the digitizer (and thus scale as $1/\sqrt{m/z}$), but it also depends on the applied potentials and other factors leading to a mass accuracy that scales as $\sqrt{m/z}$. This still means that considering the above points, mass accuracy will be better achieved at low $z$ values. The mass range limit for TOF analyzers is in theory infinite, but it is in fact limited by the detector (see below).

Orbitrap mass analyzers

Technically an Orbitrap mass analyzer could benefit from working at high $m$, low $z$ conditions, as mass accuracy in an Orbitrap scales as $\sqrt(m/z)$. The instrument is nevertheless limited by the possibility to inject ions within the trap, which is currently limited to 4,000 (or maybe 8,000, I did not check the most recent developments in the field). Thus ESI is required for such high mass systems, but the highest mass accuracies would be achieved on the high end of the achievable mass range.

FT-ICR mass analyzers

In FT-ICR mass analyzers, mass accuracy scales as $m/z$. Thus there is no effect of the charge on mass accuracy. Technically, FT-ICR instruments always include a quadrupole (trap or filter) between the ion source and the FT-ICR mass analyzer and the $m/z$ range is thus limited by the range of this filter (4,000 - 8,000).  

Other issues of high mass measurements

One of the difficulties that arises when using high mass ions is also ion detection: devices using a secondary electron emission (such as MCP's or conversion dynode) have efficiencies that depend on the linear velocity of the impacting ion. Therefore the standard detectors are not well adapted to high $m/z$ ions. Some detectors have been developped to circumvent this limitation, but this remains an issue for masses in the 2 - 10 MDa range that you quote in your question.

One other issue is ion desolvation: as size increases, adducts (with salt, solvent or matrix) tend to increase also, leading to changes in the total mass of the ions and a broadening of the peaks. Mass accuracy will also be reduced because there is no direct rule for removing the masses of these adducts from the measured mass to lead to the mass of the molecule.