Do you have the problem with the search builder interface that is too slow or after you search to get the result?
How is the advanced search behaving?
The problem is that it's hard to find what the root cause of the problem, as it's likely dependent of your configuration and how you are using civicrm.
One thing you can do is log the slow queries (it's a configuration option in mysql) that takes more than a second. It's not going to solve the problem, but at least might help you to identify the problem
And a wild guess: do you have smart groups?
These can have a massive impact on performance. ACL might be another reason that it's slow.
EDIT: more suggestions now that you confirmed smart groups
You might want to cache the smart groups for a longer period of time (say 2 hours)
Administer > Customize Data and Screens > Search Preferences
and enable the cronjob to re-build the smart groups cache every hour
As for the general speed, it's likely that you need more resources to run civicrm 4.6 compare to 4.4, if your server was already borderline too weak to handle 4.4, the new features introduced by 4.6 might be the extra nudge needed to make it trip over. It might be worthwhile investing a bit more on your hosting.