Searching for wildcarded strings -- especially with a wildcard on both beginning and end -- are not going to be very fast. You can look at the search job inspector output and see if there is anything there to point you at a specific cause, but my suspicion is this is hard to solve.
Your best bet for making this search much faster is to throw much more hardware at the problem. Add several indexers and distribute the data/search across them. Faster disks would probably help, too.