I am programming similar stuff to you while you are also working on it.

What I did was draw rooms in a map first. Then snake around tunnel elements. All these elements would be disconnected. Nu double tunnels or rooms overlapping.

Then I would pathfind each tunnel element, trying to reach the primary upstairs, until it had a dead end. It knows where the upstairs is. Each pathing attempt in a section, the dead-end usually closest to the upstairs, I would mark.

Next I went back and at marked each-dead end I tunneled to another tunnel element or room, connecting the two.

Then I would pathfind everything again with an A* and again newly mark all unconnected dead ends. If everything was connected with everything else, it would tell me and I was done.

In the end that worked pretty well. It didn't overconnect everything (a problem I had at first) and it also didn't create a linear pattern of room-tunnel-room-tunnel.

Not the most elegant, but it worked for me. Once I had it working properly, it worked pretty cool. Still, it does leave a bit of unused space (walls that never become rooms or tunnels) on the map. That, I can patchwork up.

How many iterations it takes depends on the size of the map. But for 41x41, I think it needs 3 or 4 on average.

I don't think speed is really a problem unless you have an algorithm that fails 90% of the time and has to start over and over again because it can't meet certain conditions you set.

If you want it to branch out like a tree, you can program it like that. Place a room somewhere in the middle, tunnel a certain direction for a certain distance, create another room B1. Then go back to room A, tunnel in another direction, create room B2. Go to room B1, create two more tunnels that end in rooms C1 and C2, go to B2, create C3 and C4, etc.