When you have a Workflow or Report performance problem, go to Manage > Monitor > Performance Profile and take a close look at the Performance Profile information.
For Workflow rules, we capture the time required to perform each step of the add, update, or delete operation. We also capture the time required to perform each step of the workflow rules triggered by the add, update, or delete.
For Reports, we capture the time required to perform each step of the Report.
We have spent a lot of effort to make the performance measurements accurate. We attempt to capture the elapsed time down to a resolution of one to two milliseconds. Admittedly the detail can be overwhelming, but the benefit of these very fine grained measurements is that they normally reveal exactly where the time is going.
Often you will find that time is being consumed computing virtual columns or expressions. This is especially true if these computations require that we read other tables to compute the virtual column or expression. Armed with this information, you can often improve your expressions to make them more efficient.