How difficult and expensive would be to build some kind of pod on the bottom of the ocean, accessible only by submarine? And would there be any rules governing structures on the sea floor in international waters?
I think there is a regulation that says these must be built by offshore labor, right? 
Here’s one that’s in operation: Aquarius.
It doesn’t quite meet your criteria: it’s only 20 meters below the surface, which means it’s accessible to a scuba diver - and a full-sized submarine would probably not have much interest in operating in water that shallow.
The article seems to indicate that it costs about $10,000/day to operate.
The International Union of Merfolk?
The US Navy tried a number of experimants like this in the 60s, with SEALABs I, II, and III. It didn’t work really well. SEALABs I and II were reasonably shallow, at 58 and 62 meters, respectively, but SEALAB III was at 185 meters, leaked immediately, and killed one of the divers assigned to the project.
Overall, better to buy a nice deserted island and build your Lair of Doom[sup]TM[/sup] there.
Oooh, “Crisis on conshelf ten!” 
Erm, sorry. Just to throw in one other tidbit, you’d probably need to use pressurized gases matching water pressure in your lair, since buidling the pod walls AND submarines to stand against that kind of pressure would be way too difficult and expensive.
And then, you need to worry about an escape route that doesn’t involve coming back to the surface, because of the decompression time thing.
(Assuming that you might need an escape route - but all the best lairs have one.)
There’s Jules Undersea Lodge at 30 feet, and two more extensive underwater hotels planned, but likewise at fairly shallow depths, Poseidon (PopSci article) and Hydropolis. Both are big on plans but keep costing more and more money.
I’d say there’s little to no advantage for a renegade meglomaniac to building a permanent structure underwater compared to just building a submarine.
[Christopher Molitsanti]That was real? I thought it was just that cartoon![/Christopher Moltisanti]
You’d be thinking of Sealab 2020 or Sealab 2021, then…
I’ve about given up trying to construct a good undersea lair in central Ohio.
The Sealab program ran into many unexpected problems.
Just a few million years too late. A shame… Dunkleostei with friggin’ lasers on their heads would make a great lair defense system.