I’ve written a dex-method-counts tool that outputs per-package method counts faster and more accurately than the smali-based tools referenced in JesusFreke’s answer¹. It can be installed from https://github.com/mihaip/dex-method-counts.
[1] that script disassembles the .dex and re-assembles it by package, but this means that methods that are referenced by multiple packages are counted twice