How does rate of evolution/innovation scale with population size?
Interesting question (+1) but not that easy to answer. I'll give a try! 

First, the rate of evolution and rate of adaptation are two different things.

There are two main thing processes that quantitatively differ in populations of different sizes. 1) population-wide mutation rate and 2) genetic drift.

1. Population-wide mutation rate

Large populations create more mutations at each generation and therefore if the rate of evolution or the rate of adaptation is limited by the genetic variance, then one can expect large population to have higher rate of evolution and higher rate of adaptation.

--> Large populations may have higher rate of evolution and higher rate of adaptation

2. Genetic drift

However, small population have higher drift, resulting in a higher probability of fixation for new neutral (or slightly deleterious) mutations. It results that a small population will fix (fixed: frequency = 1) a higher proportions of the new mutations through time than large populations.nActually the probability of fixation of a neutral mutation is \frac{1}{2N}. Therefore, the rate at which neutral alleles fix is $\mu\cdot 2N \frac{1}{2N} = \mu$, where $\mu$ is the mutation rate. So, the rate of fixation of neutral alleles is independent of the population size.

--> Small populations have more drift but this doesn't necessarily yield to higher rate of evolution

Other and comments

Shifting balance theory

If adaptation is limited by the genetic architecture, that is, only mutation of very big effect on phenotype can be advantageous, then small population have the advantage to be able to accumulate slightly deleterious mutations, so that they can get off a local peak on the adaptive landscape and eventually manage to evolve toward a new higher fitness peak.

--> Small population may have higher rate of adaptation

Population-wide mutation rate vs genetic drift

Weighting the relative importance of rate of production of neutral (or quasi-neutral) mutations (See population-wide mutation rate above and the probability of fixation of neutral (or quasi-neutral) mutations (See Genetic drift above) depends also on the probability distribution of mutational effects (=probability distribution of the effect on fitness of a given new mutation).

Ceteris Paribus

The comparison between large and small populations are dependent on the state of other parameters. So even when saying all else being equal (ceteris paribus), we need to know what these other parameters are equal to, in order to answer the question because there are interactions between populations size and other parameters in explaining the rate of adaptation and rate of evolution.

Other impact of population size on genetic features

Population size has many impacts on various genetic features, such as pattern of genetic diversity, distribution of per locus Fst between subpopulation, and other things. This paper is likely of interest