No explanation of the name Úlairi is ever given, and its intended meaning is very uncertain. One possibility derives from the use of ul- as meaning 'monstrous, horrible' (as for example in the name Uldor). On this model, the final element -airi is perhaps related to Quenya aira, 'eternal, unending', so that Úlairi would mean something like 'undying monsters' (a fair description of the Nazgûl).
This is far from a sure interpretation, and others could be invented. Another possibility would be based on ú- 'not' and lairë 'summer', suggesting that these were creatures of darkness and misery, but that interpretation seems a little too contrived to be very plausible.