As well as what James K has said, another way to think about it is that you're taking a simple statement of fact:
They are coming sooner than expected
and using may to talk about the chance this might happen instead:
They may be coming sooner than expected
As James said, may is followed by the infinitive, so are becomes be. The rest of the sentence stays the same, because really all you're doing is changing the verb phrase so it sounds less like a sure thing, and more like something that's possible.
You could say may come instead, but that's the may form equivalent to will come. They may be coming is equivalent to they are coming. Both express the future, but in subtly different ways, and the may forms reflect those meanings (just with an element of "there's a chance" added!)