How much mass can colliding black holes lose as gravitational waves?

Suppose you have two black holes of the same mass $M$ and $m = GM/c^2$. The radius of each black hole is then $r = 2m$, and the horizon area is $A = 4\pi r^2$ $ = 16\pi m^2$. Two constraints are imposed. The first is that the type-D solutions have timelike Killing vectors, which are isometries that conserve mass-energy, and with the merger the gravitational radiation is in an asymptotically flat region where we can again localize mass-energy. So the initial mass $2M$ is the total energy. The entropy of the two black holes is a measure of the information they contain and that too is constant. So the horizon area of the resulting black hole is the sum of the two horizon areas, $A_f = 2A$ $ = 32\pi m^2$, that has $\sqrt{2}M$ the mass of the two initial black holes. Now with mass-energy conservation $$ E_t = 2M = \sqrt{2}M + E_{g-wave} $$ and the mass-energy of the gravitational radiation is $.59M$. That is a lot of mass-energy!

This is the upper bound for the generation of gravitational radiation from mass. The assumption here is that the total entropy of the two black holes equals the entropy of the final black hole. Physically this happens if all the curvature exterior to the merging black holes does not result in mass-energy falling into the final black hole. There would be back scatter of gravitational radiation, much as one has to be concerned about the near field EM wave near an antenna that can couple back on it. The final entropy of the merged black hole will in fact be larger, but of course not larger than the mass-squared determined area of the two black holes. This means $1.41m~\le~m_{tot}~\le~2m$.

To estimate this requires numerical methods. Larry Smarr pioneered a lot of this. So far estimates run around $5\%$ of the total mass of the black holes is converted to gravity waves. in this LIGO paper two black holes of mass $39M_{sol}$ and $32M_{sol}$ is computed to have coalesced into a final black hole of $68M_{sol}$, which radiated $3M_{sol}$ is gravitational radiation and accounts for $4.2\%$ of the initial mass. This is about in line with most numerical studies. Consequently a lot of the spacetime curvature generated by these mergers falls back into the final black hole. In terms of area the initial horizon area is $4066M^2_{sol}$ and the final horizon area is $4624M^2_{sol}$, which is an additional area $558M^2_{sol}$ of horizon area with $S~=~k A/4L_p^2$ as the entropy.

The total surface area of the event horizons never decreases.

We won't consider charged black holes, since in real life, black holes never have very large charge. However, they can have very large angular momentum, as LIGO showed.

The horizon area of a rotating and uncharged black hole (the Kerr metric) is $$ 8 \pi M \left(M+ \sqrt{M^2 - a^2}\right),$$ where $a = J/M$, $J$ being the angular momentum.

So for an uncharged black hole of mass $M$, the area of the event horizon is somewhere between $8\pi M^2$ and $16\pi M^2$, where the angular momentum is respectively $M^2$ (the maximum $J$) and $0$ for these two cases.

Thus, you might be able to collide two extremal rotating black holes of mass $M$, and obtain a non-rotating hole of mass $M$, meaning that you lose half of the total mass in the collision. This scenario is where the largest percentage of combined mass is lost, because $$ \frac{\sqrt{x+y}}{\sqrt{2x} + \sqrt{2y}} $$ is minimized when $x = y$. I don't know whether such a collision is possible.

See also a separate related answer by Patrick Gupta, second answer to Did merging Black Holes in GW150914 give up entropy and information to the gravitational waves, since they lost 3 solar masses? (the question was faulty). He calculated the final horizon area for the rotating case, with entropy 1.57 times the original entropy, so entropy did grow, and the second law of BH thermodynamics held up. Using the Kerr solution and equations for the horizon area, as Peter Shor did, is important to do because unless it is a heads on collision (very unlikely) and there was no individual rotations to begin with, the final black hole is very likely to have a significant angular momentum. It is interesting, and should not be surprising, that the observed merger led to the high angular momentum (a=.67) observed in the final black hole.

Worth noting that Hawking derived first the limits for both rotating (edited, as indicated correctly by Michael Seifert in a comment below) and non rotating bodies in 1971 Phys Rev Let, and published more in 1972 for both rotating, non-rotating, and charged bodies (though he may not have been the first on the latter) in the Les Houches Summer School Lectures on Black Hole in 1972. For rotating Kerr black holes the max is just 50%, and for rotating and charged Kerr Newman black holes it's approx. 65% max.

The many numerical and PN calculations done (by Smarr and others), as stated by Lawrence Crowell in his nice answer, over the years and before the LIGO finding eventually led to an understanding that 5% or so was a more likely number in many cases (not sure if those include charged, those are not likely to occur astrophysically).

It's worth noting also that for LIGO they could not get a measurement/estimate of the initial BH rotations, if any, and estimated it would have made only a small difference (smaller than the mass uncertainties estimates) on the final estimate for the radiated grav energy. In later observations they expect to see more earlier and maybe get any pre merger rotation rates.