I have had several issues where I thought increasing quick-check's num-tests argument would increase the time taken linearly, but surprisingly it grew quadratically. This is related to the auto-increasing of the size to call-gen, which I believe it isn't documented well enough. It also seems like other people have had trouble with this functionality, see the reply to announcement of clojure.test.check.
Preferably, it should be mentioned in the docstring and the tutorial that the size of the structures generated grows linearly with the amount of tests you have, up to 200. As a result, doubling the amount of tests does not necessarily double the amount of time taken to run the tests.
In some of my tests, this behaviour increases the running time exponentially, and I actually used quite some time figuring out why. The documentation on recursive generators decreases the size of the binary tree in half, but it is not explained why it is split in half. While obvious in hindsight, explicitly explaining that recursive structures should have an amount of nodes proportional to the input size argument and how it is done, would be beneficial.