Skarpi is mentioned many times before appearing in the first Kingkiller book. He's mentioned as friend of Kvothe and as a companion of the Chronicler. But his only interactions with Kvothe in Wind are in chapters 26 and 28. In neither (as far as I can find) does Kvothe give his name to Skarpi. Yet at the end of chapter 28 when Skarpi is being arrested on trumped up charges of heresy, he uses Kvothe's name when telling him to run. How did he know it?
At that point in the story, Kvothe is an orphan running free in the city of Tarbean. The place where he often sleeps and helps around, though, is at the home of the priestly man called Trapis.
Kvothe suspects that Trapis might be Tehlin Priest. Scarpi is Tehlin Priest. More importantly, both characters tell stories to children and Scarpi is later arrested as a heretic during one of the storytelling sessions. Trapis is confirmed by Rothfuss in this interview to be a disciple of a schism of Tehlinism referred to as the Mender Heresies.
Basically, Trapis practically knows all the beggar children of Tarbean. He occasionally tells them stories and tells them when Scarpi is in town and telling stories to children.
It is never explained in the books how Scarpi knows Kvothe's name, but my guess is that he just asked Trapis. Their names are quite similar and I guess they might either be brothers by blood or brothers by faith. Both seem to be members of the same schism of Tehlinism.
Other theories are that Skarpi is really Selitos, the famous Namer and that he actually saw Kvothe's true name and so called him by it. The other theory is that Skarpi is really Taborlin The Great, another great Namer, and that he knows and sees true names of everyone.
Truth be told, we don't have confirmation of any of that and Kvothe is somewhat of an unreliable narrator.