I'm not sure that making them spotlights will have too big an impact. Another thing to consider is that performance is not directly proportional to poly count (if anything, the node count is more indicative of performance -- so I understand). Also, further to what Duke said in another thread, the way that your BSP gets chopped up has a big impact on performance; if you've made your terrain too complex, that could affect the FPS.
One last thing -- I've always found terrain to cause slowdowns if you have a large expanse of it in view at any time, regardless of other factors. You may have to find ingenious ways to block off parts of the terrain from other parts; possibly make the dunes in the middle higher?