Logistics regression with polynomial features vs neural networks for classification
I expect what he's referring to is the combinatorial explosion in the number of terms (features)
as the degree of the polynomial increases. 

Let's say you have $N$ measurements/variables you're using to predict some other variable.  A $k$th degree polynomial of those $N$ variables has $ N+k \choose k$ terms (see here).  This increases very quickly with $k$. 

Example:

Say we have N = 100 variables and we choose a third degree polynomial, we'll have
 $ 103\choose3$ = 176,851 features. For a five-degree polyomial it goes to:
$105 \choose 5$ = ~96 million features.  You'll then need to learn as many parameters as you have features.

Compare to a NN:

Compare this to using a fully connected NN
say we choose K fully connected hidden layers with $M$ units each.  That gives:
$ (NM) + (K-1)(MM) + M$ parameters.  This is linear in $K$ (though the $MM$ term attached to it might be big).

For N = 100 variables again, two hidden layers, and 350 features nodes per layer we get 157,580 parameters - less than we'd need for logistic regression with third degree polynomial features.

Representational power

(Added this section after seanv507's great comment)  * See caveat below

The argument above was just a numbers game - how big of a NN can you get while still having the same parameter count as logistic regression with polynomail features.  But you're getting at something when you say in your question:


  I mean, when we talk about neural networks we're usually looking at a
  model with a very large number of parameters so why would logistic
  regression be more computationally expensive?


Well said.

Efficiency

Neural nets are universal function approximators, and we know that polynomials can approximate functions too.  Which is better? What should one use? I'd bet that, for a given parameter "budget", a NN could better approximate "more" functions than a polynomial with the same number of parameters.  It wouldn't surprise me if there was theory to back it up, but I don't know it off hand.  seanv507's statement


  One possibility is to assume that the nonlinear activation function is quadratic...and identify what range of polynomials the NN could represent.


is an interesting idea.  Empirically, NN's have done better for many hard tasks than polynomial representations, and that's pretty strong evidence.

*Caveat

As seanv507 says - this is the hard part.  The above statements won't always be true - I'd argue they're probably mostly true.  If a low-degree polynomial basis nicely and reliably separates your classes, then it's probably worth using / trying polynomial features.