Recently I have had trouble finding the shares to short for positions I want to take at the start of open hours. Is it easier for a broker to find the shares in premarket when the stock is likely to increase volume heavily at the start of the day?
The shares available to short are a portion of those shares held by the longs.
This number is actually much easier to determine outside of active trading hours, but either way doesn't really impact the matter at hand since computers are pretty good at counting things.
If your broker is putting up obstacles to your issuing sell short limit orders in the pre-market then there is likely some other reason (maybe they reserve that function to "premium" account holders?)
I don't think that the trading volume would impact a broker's ability to find shares to short. You might think that a lot more people are trying to short a stock during regular trading hours than in the pre-market, and that's probably true. But what's also true is that a lot more people are covering their shorts during regular trading hours than in the pre-market. For stocks that have difficulty in finding shares to short, any time someone covers a short is an opportunity for you to enter a short.
If you want to short a stock and your broker is rejecting your order because they can't find shares to short, then I would recommend that you continue placing that order throughout the day. You might get lucky and submit one of those orders right after someone else has covered their short and before anyone else can enter a short. I have had success doing this in the past.