In his Polyhedral Computation textbook, Fukuda writes:
It is known that the counting problem [of perfect matchings] is #P-complete even for bipartite graphs. There are polynomial algorithms for the listing problem.
But, if I can list all matchings efficiently, I also can count them efficiently (right?). Seems I'm missing something, but I don't see what... (and I'm not very familiar with the #P-complete class)
The complexity of counting and of listing is evaluated differently. An algorithm listing all the possibilities is usually called an enumeration algorithm. (This can be confusing because outside computer science, "enumeration" can also refer to counting, as in "enumerative combinatorics".)
When we want to list all the perfect matchings, a polynomial-time algorithm is an algorithm with a polynomial-time delay between matchings. In other words, we want an algorithm that goes through all the matchings one at a time, such that the time between listing consecutive matchings is bounded by a polynomial in the input size.
This would also give us a polynomial-time algorithm for counting perfect matchings if the total number of matchings were polynomial. However, in some cases, it can be exponential or worse; for example, the complete bipartite graph $K_{n,n}$ has $n!$ perfect matchings. So even if we can list all those matchings with only a polynomial delay between each one and the next (and even if it took us only $O(1)$ time at every step!) it will take us too long to count them that way.