How to find an MCU with specific characteristics?
The strategy would indeed be to go to the various manufacturer web sites and use their parametric search engines to narrow down the selection to 4 UARTS. Each manufacturer will have a slightly different search facility so you have adapt to that. 

One benefit here is that the number of main MCU manufacturers has been reduced in the recent decade due to companies either joining forces or some exiting the market.

For small footprints it can often be useful to consider the SiLabs1 offerings. The Leopard Gecko series of ARM core MCUs offer five UARTs in QFN64 or QFP64 packages.

1No affiliation with company but user of their products.