How do pool operators do their hashing? For every "getwork" served by the pool, a Merkle root must be calculated for a block.  The run time of SHA-256 is proportional to the number of "chunks" of 256 bits, and a typical block will have thousands of these chunks (a block header has just has three, after preprocessing).  So the pool operator will need hashing power in the Mhash/sec range, roughly.  Am I right so far?

The individual miners need much more hashing power, but in a simpler form: here's a three chunk preprocessed block header; hash it with each of 0000_0000x through FFFF_FFFFx in the nonce field.  If hashing engines specialize on that simplicity, to make them cheaper and/or faster, then they don't work so well for the pool operators.

So if I'm a pool operator, or a solo miner, and I need to generate millions of Merkle roots, what are my options? Do the hashing engines (CPU/GPU/FPGA/ASIC) have an API I can use?
A pool will generally create a unique merkle root for each getwork request by a miner.  If it accepts difficulty 1 shares, the miner can spend an average of about 4,000 Mega-hashes on that block (and will earn an average of 1 share per getwork).

To create a block header for each miner, the pool operator changes some unique information in the first (generation) transaction of the block, and then rehashes the block to create the merkle root.  If done naively, this will take O(N log N) sha256 hashes (where N is the number of transactions in the block being mined).  By saving some information from computing the last merkle root, you can recalculate a change in the generation transaction with only O(log N) hashes.

With hundreds of transactions per block the ratio of hashes performed by the pool operator and the miners is over 100 million to 1.

For an even greater savings, pools can accept a getblocktemplate api request instead of a getwork request.  This mode allows the miner to generate his own block headers and mine for an average of 10 minutes before needing to be refreshed by the pool.