Did Pokemon even get featured on the App Store? Once your name recognition is big enough, traditional marketing is just rounding error.
Just checked and here in the UK Super Mario Run already has a banner feature and is top of the new games we love section despite not being available yet to play yet