Player A joins the ''player search que", 45 secs later Player B joins the Que....and within 2-5 secs they find each other. Is that doable?

Yes, it is doable, if you have enough players.

As hplus0603 points out, its all about the probability that another player actually will join within 45 seconds.

With too few players, that probability is too low, so most of the time another player will not join the queue within time.

Others can probaby give you a more accurate calculation, but if you consider that in 8 hours you have 640 "45 s slots", it should be pretty easy to see that distributing 1000 players randomly among those 640 buckets will have a high probability of players being alone in their bucket.

Now the players aren't perfectly randomly distributed, there are highs and lows, but that just makes the problem worse in the lows.

(the bucket approach is a pessimistic estimate, since two players in neighbouring buckets might be within 45s of each other, but I think it still is useful to understand the scale)

You really have to answer two questions:
1. How long will a player wait for the next player?
2. How many players will look for other players in a given time period?

That's all based on testing for sure.

I'm just trying to do less work that isn't needed if possible. Idk if you play league of legends, but when a player joins a que it will state something like "avg time to start game: 1:30" or some reference to that. But when you actually do join, the timer goes well passed that to 3-5 mins...etc.

Don't think to detailed with that, the point I'm trying to make is the fact of a timer. So something like "Player search takes 5sec to 1m to find a player". Now that might help and keep players ON the app to wait.

My strengths are marketing / publishing / project management so bringing players to the app isn't a HUGE deal in my eyes, but since this is my project personally, I'm trying to see the behind the scenes side of things when it comes to functionality and making sure it's simple for the players.