Redis overall isn't really good at wildcard / patterns based commands. It's totally possible to do so, but do to the tradeoffs that Redis makes and fundamental algorithmic complexity issues, it's never going to be as fast as using Redis for what it's really good at.
Keys vs Scan:
The biggest difference between the two is that KEYS loops over and checks every single key without pause, while Scan checks a few keys at a time.
When you have a lot of keys checking all of them can take a relatively long time. Redis makes a lot of design choices assuming, that you're running a large number of short to run commands, rather than a few very long ones.
Redis only runs a single command at a time, so long commands, can cause others to queue up behind it.
By using SCAN, your wildcard delete will still take a long time, but it will allow other commands to the Redis server to run in between scan calls, without there ever being a big long command queued in front of it.
Another option would be to keep track of all the keys you might want to delete when you're adding them, rather than by pattern checking later. This would only work if it's predictable which keys you'd later want to delete. You'd need to build a custom index structure, based on the needs of your business case, but if that potentially interests you, I'd suggest giving Itamar Redis index slides a look as the first step down that Rabit hole.
http://www.slideshare.net/itamarhaber/20140922-redis-tlv-redis-indices