Poor push performance with large number of refs

I have a repository that's just under 2 GiB in size and contains over 20000 refs, with a copy of it on a server. Both sides are using Git 2.1.2. If I push a branch that contains a single commit, it takes about 15 seconds to push. However, if everything is up-to-date, it completes within 2 seconds. Notably, HTTPS performs the same as SSH.

Most of the time is spent between the "Pushing to remote machine" and "Counting objects", running git pack-objects:

  git pack-objects --all-progress-implied --revs --stdout --thin --delta-base-offset --progress

Unfortunately, -vvv doesn't provide any helpful output. I have some suspicions what's going on here, but no hard data. Where should I be looking to determine the bottleneck?

  brianc no # time git push -vvv remote-machine:/tmp/testcase +HEAD
  Pushing to remote-machine:/tmp/testcase
  Counting objects: 1, done.
  Writing objects: 100% (1/1), 184 bytes | 0 bytes/s, done.
  Total 1 (delta 0), reused 0 (delta 0)
  To remote-machine:/tmp/testcase
   + 5059893...2db9804 HEAD -> test (forced update)
  git push -vvv +HEAD  12.35s user 1.61s system 91% cpu 15.337 total
  
  brianc ok # time git push -vvv remote-machine:/tmp/testcase +HEAD
  Pushing to remote-machine:/tmp/testcase
  To remote-machine:/tmp/testcase
   = [up to date]      HEAD -> test
  Everything up-to-date
  git push -vvv  +HEAD  0.50s user 0.22s system 51% cpu 1.408 total