By Alison Sider

Airlines are preparing to cut thousands of workers and tap government loans as a surge of coronavirus cases and fresh government travel restrictions upend a nascent recovery in travel.

After New York, New Jersey and Connecticut said last month they would require people arriving from hot-spot states to quarantine for 14 days, United Airlines Holdings Inc.'s reservations for travel within the coming month quickly began to slide, according to a presentation to United employees Monday viewed by The Wall Street Journal.

The drop-off has been most acute at United's Newark, N.J., hub, where near-term net bookings were about 16% of a year earlier's levels as of July 1, according to the presentation. Just weeks earlier, net bookings there had climbed to about a third of last year's levels. The bookings metric, which is the difference between new reservations and cancellations, has also started to fall in other hubs, the airline told employees.

That is a worrying sign for the struggling airline industry's hopes for a recovery. Denver-based Frontier Airlines also told employees this week that bookings had taken a hit, and that it is evaluating what schedule reductions it would need to make as a result.

United shared the more dire outlook with many employees across the country Monday as it told them to prepare to receive notifications of potential furloughs under the Worker Adjustment and Retraining Notification Act, known as the WARN Act, as soon as this week.

The airline told employees that tens of thousands of employees would receive such notices. The exact number couldn't be immediately determined, and it isn't clear how many will be let go. Airlines including United have offered early retirement and buyout packages to encourage workers to leave on their own.

Most airlines, including United, have cautioned workers they would have to reduce staff on Oct. 1, when the restrictions that accompanied $25 billion in federal aid are lifted. United has already said it plans to cull its management and administrative workforce by 30%. Delta Air Lines Inc. last week sent similar notices to over 2,500 of its pilots.

Airlines are also lining up another $25 billion in federal loans that were authorized under the same broad stimulus package approved in March, as they stockpile cash to weather a crisis that they have said will likely last years.

United, Delta, Southwest Airlines Co., JetBlue Airways Corp., and Alaska Airlines have signed letters of intent with the U.S. Treasury Department to obtain the loans, the Treasury said Tuesday. Five other airlines, including American Airlines Group Inc., signed letters of intent last week.

The Treasury didn't detail the terms of the loans but said the borrowers would have to provide warrants, equity stakes, or senior debt instruments, as well as agree to limits on executive compensation and share buybacks, among other requirements. United has previously said it would be eligible for up to $4.5 billion in loans under the program. Airlines have through the end of September to decide whether to draw the funds.

Planning for the future has become more difficult for airlines in recent weeks as the outlook has become murky once again.

After passenger volumes tumbled by 96% in April, demand had started to thaw more quickly than some analysts were expecting. New bookings began to overtake cancellations, planes began to fill up and carriers started to add more flights, setting expanded schedules in some cases through August. Over 760,000 people passed through Transportation Security Administration checkpoints on Thursday heading into the July 4 weekend -- the highest since March.

Now states and cities are clamping down on travel from new coronavirus hot spots. Chicago is also requiring visitors from 15 states to quarantine for two weeks upon arrival, as is Pennsylvania.

At the same time, businesses and attractions that had been planning on reopening are having to shut down again in hard-hit areas. Miami-Dade County Mayor Carlos Gimenez on Monday rolled back reopening there, ordering gyms to close and restaurants to limit service to takeout and delivery, starting Wednesday. Walt Disney Co. 's Disneyland resort, which was slated to reopen July 17, will remain closed until an unspecified date, the company said last month. Texas also paused its reopening.

All of this has made travel both more complex and less appealing. Some see similarities to the beginnings of the pandemic's spread, when demand dried up rapidly over the course of just a few weeks and airlines had to swiftly cut schedules to keep up.

"It's March all over again," one senior airline executive said.

Lupe Garza was planning to fly from Dallas to California on Wednesday for a vacation in Los Angeles and San Diego. But on Monday he said he decided that with new restrictions that mean many bars, restaurants and other businesses would be closed, it wasn't worth it.

"Literally nothing to do," he said. "I was afraid if I did fly over, they could make travelers from Texas/California quarantine again...which would be awful," he said.

--Kate Davidson contributed to this article.

Write to Alison Sider at alison.sider@wsj.com