One thing that surprises me about the speculation here and in the setlist thread is that nobody (myself included) is entertaining the possibility that they do five songs from one album and then five songs from the other album all clustered together. If they really are doing five each like some folks think, it could make sense as they can also alter the stage like they did on LOTB.
It's interesting that everybody is coalescing around Loneliness as a song that has a high chance of being played. I would be delighted to hear it, although a big part of me feels like you could've asked Steve about any song in that interview and he would say "we should play that." Kinda reminds me of when he said he wishes they played Only the Good Die Young. Well, why don't you? That would be a real setlist highlight though, and it is a song that has only been played one more time than Alexander.
I went back and looked at my original setlist prediction, which is pretty conservative. No Alexander the Great, only four songs from Senjutsu including one they played already, and a couple "old reliables" to fill out the set. I mostly stand by that prediction, although I think I mostly missed on Senjutsu. While I think Writing on the Wall stays, I can see them pulling out another epic (I'm starting to feel pretty bullish that both Hell On Earth and Parchment will make the set).
@Diesel 11 posted some really nice stats on the setlist prediction thread and only 9 people have Darkest Hour in their setlist. I. could see this being a pretty big dark horse pick, as it is a pretty simple and slow song that might be easy for the band to put together quickly, which leads me to my final point:
The trickiest thing about predicting what they're going to play is that by the very nature of the theme it seems like this show is going to require much more rehearsal time than Maiden usually allots time for/what they seem willing to do. Both albums contain some of their most complicated material and both albums contain a whole heap of songs that have either rarely been played live or never been played live (given that they recorded Senjutsu 4 years ago now, re-learning some of those songs is probably going to be a similar undertaking to relearning Alexander the Great or anything else off that album). I have a hard time believing that they are going to even want to rehearse and pull off Parchment, Alexander, CSIT, Loneliness of the Long Distance Runner, etc etc. These are among the most complex and technically demanding songs in their catalog, which makes me feel we're more likely to just get one or two. But at the same time, I don't think they would agree to a tour like this if they weren't prepared to put that work in. I think the people who suggested they've been rehearsing some of these songs already may be on to something. I can imagine that they would only agree to a tour like this after successfully rehearsing some of those Somewhere in Time songs at soundchecks on the previous tour. We'll see, I'm getting really hyped about it!