I think the phrase "Majority English-speaking" sounds awkward, mostly because "majority" is more often used as a noun. So it feels like the words are in the wrong order, and it's not clear what is meant. For example, "The English-speaking majority", does imply that the majority of people in that area speak English, but the focus is on this particular group and not on the area as a whole.
Without any context, if I read "Majority English speaking", I would think someone was trying to say "The English-speaking majority", which would be confusing.
Of course, since it appears in a UK government pamphlet, it's obviously used and meaningful to the people in and around the agency who published the document. But government officials often use jargon that makes perfect sense to them, but leaves the average person scratching his head.
As wordy as it may sound, it would have been better to say:
Countries where the majority of people speak English.
Countries where English is the dominant language.