I'm currently reading TBotNS. I keep getting struck by parallels with AEG, which I have just read.
It has already been noted that the role of the malign underwater Storm God of AEG is similar to that of Abaia in the Urth Cycle, but some of the parallels are even more specific. Compare, for example, Severian's dream of the sunken city in chapter XV of Shadow, "Baldanders", with the dream of the underwater city that Cassie experiences when she holds hands with Pat Gomez in chapter 22, "The City under the Sea", in AEG.
Then there's Dr Talos' transformation of the skinny waitress into the voluptuous Jolenta. His purpose is to create a female star for his play. It's very similar to what Gideon Chase does for Cassie in AEG.
I haven't thought through the similarities and differences between the flood apocalypse of UotNS and the closing section of AEG, but I am wondering about possible similarities between the roles of Vodalus and Gideon Chase. Both appear to be working to undermine a powerful ruler (the Autarch, Bill Reis who is King of Takanga) whom they subsequently turn out to be serving. Both pay the hero/heroine a fee to recruit them to their side at the start of their respective stories.
Nigel