(cl-ppcre:scan "^\[([^ ]{1,})+[ ]*(.{1,})?\]" "foo [[Main]] [http://baz%5D%27%27bold%27%27%27%27%27%27%27bar''''" :start 13)
This is a regular expression that does lots of backtracking when it fails. If you change that you'll most likely see a large performance improvement.
A small change is to simplify the first grouping:
"^\[([^ ]{1,})[ ]*(.{1,})?\]"
The reason that having :start is so much slower is that the regex matches a different string that needs far less backtracking that without the :start.
Cheers, Chris Dean