If you want to go this route, make sure to work with people who can show you clear metrics of their influence - I think it goes without saying, but many people with a massive amount of followers have purchased a lot of them to look more influential than than they are. A huge following with very low engagement is worthless. Anyone worth working with should be keeping track of metrics already.
I would also recommend working with influencers who are personally excited about your product. I think it comes through (unless they are crazy-good at copywriting) when influencers promote stuff just because they are being paid vs when they genuinely love the product.
I think the secret to great success is knowing your own target audience really really well, so that you choose the right influencer for max ROI.
For apps, its very important that you try a group of smaller influencers first. Cheaper and will provide good insights into what a bigger influencer might bring in. Start small.
:)