I'm gonna go out into wild theory land, so please feel free to ignore this If crackpot theories aren't your thing.
Anyways.
The Parshendi have a huge focus on music with the rhythms and things right? Well, music is full of patterns. Once you play or sing for a while, you find patterns that repeat across all sorts of songs and pieces. For example, the I-IV-V-IV chord progression in literally every song ever. Gradually, you learn to pick up on these patterns and anticipate them. My point is, a background in music could make the parshmen very good at noticing patterns, which are a huge thing in language.
They could also just have really good flashcards.