Currently Murandy seems most likely as a power base of Demandred. We know that King Roedran is gathering an army in Lugard since WH (the very book where Demandred states that he is currently very busy in WH, ch. 13). It also seem strategically quite advantageous, especially if Semirhage would control the Seanchan in the south, Mesaana the AS in the north and Moridin the Black Tower in Andor; plus Masema probably also being under Demandred's or another Forsaken's control. Furthermore it's said in CoT, ch. 14, that King Roedran had a spy in the Caemlyn Palace, and we know that Demandred is interested in Andor and was responsible for watching Rand, together with Osan'gar. Finally, one of the two copies of Fog and Steel might have been made to be read by the General Demandred (if King Roedran is his proxy and got the other copy).

Besides Murandy, especially Shara or the Land of the Madmen are mentioned as possible bases of Demandred. But IMO these theories have their problems, especially that those lands seem to be too far away from the actual battlefield in the Westlands. We also have no indication that Demandred controls the Borderlander(except Graendal thinking he might be there after all) or Whitecloak army, especially since we got PoV of leaders there.

Alternatively or additionally to Demandred's power base in Murandy, I would suggest that he is located in Tarabon/Tanchico. We know that the country got a new King by the Seanchan since ACoS, but otherwise we don't really know much what is currently going on there (Ituralde made a bit chaos among the Seanchan there, though). Certainly the population of Tarabon has quite a potential to gather a big army. Besides that, we know that there are many Dragonsworn in Tarabon and on the Almoth Plain (Masema states that shortly before his death). Thus Demandred could be the one who is gathering the Dragonsworn there.

This would explain Sammael's comment about Demandred's dangerous "friends" in the south, and that Demandred states in TGS, prologue: " We will be ready", which rather points to a certain group being under Demandred's thumb, IMO. Demandred could either control the new King of Tarabon and/or the Dragonsworn from the shadows or - as I suggested a few times in the past on the old WoTmania board - even pose himself as the Tarabon military leader "Tamrin", maybe now being the leader of the Dragonsworn. Tamrin is just mentioned in TSR, ch. 38, but doesn't appear on-screen; RJ actually stated, though, that we haven't seen Demandred's alter ego on-screen yet.

Demandred (additonally) controlling Tarabon and/or most of the Dragonsworn in the south-west, would nicely tie in with the idea that Demandred is the one who controlled Masema and that he created chaos in LoC. Finally, there is still this mysterious torturer from Tarabon, Jaq Lounalt (now working for Elayne), who might be a provided spy of Demandred then.