"What other games do you play aside from Tetris?"
In this sentence, other means any game except the one mentioned (Tetris). Similarly, aside from means any game other than Tetris. If I omit the other, the meaning doesn't seem to change.
Does this mean that having both words in such a structure is redundant? If yes, then why are these sentences very common and why haven't I seen anyone point out this mistake?
Is it redundant - yes.
Is it "wrong" - no.
We often use phrasing that is redundant for the purpose of emphasis.
What other games do you play aside from Tetris?
It's also likely that the speaker/writer wants to emphasize the "otherness" of the games. Perhaps the original intent was to say "What other games do you play?" and the remainder of the sentence was added for clarity.
What other games do you play... aside from Tetris?
Would it be OK without "other? - Yes.
What games do you play aside from/other than Tetris?
They are both right, but the meaning is different.
If you ask "What games do you play aside from Tetris?", the question implies that you already know I play Tetris, and also that I play other games. If I answer "none", I am contradicting the assumption that is in your question.
Asking "What other games do you play..." only implies that you know I play Tetris. If I answer "none", I am giving you information, but I'm not contradicting anything that you have already said.
Questions like "What games do you play aside from Tetris?", where the question implies part of the answer, are called leading questions. This is a fairly innocuous example of a leading question, but some situations (e.g. in a law court) asking leading questions is not permitted - the standard example of such a question being "When did you stop beating your wife".
