Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace
Eventually I ended up solving this for $O(n)$ gates. I wrote up a trilogy of blog posts on it.


Constructing Large Controlled Nots (classically, with an ancilla)
Constructing Large Increments (classically, with an ancilla)
Using Quantum Gates instead of Ancilla Bits


Of course it would suck if you found this twenty years from now and my website was long gone, so the basic steps follow in quickly-described image form.

1. Bootstrap a Borrowable Ancilla Bit

Use a square root and its inverse to reduce the maximum number of controls  by one, creating an uninvolved wire for each operation. Then iteratively move controls off of non-Not operations, and re-arrange the cruft that results into large increment gates and single-qubit phase gates.



2. Use Single Ancilla Bit to Cut Operations in Half

For each large operation, use the uninvolved wire as a borrowed ancilla bit. Use it to transform the huge increment and controlled-not gates into smaller operations that each have approximately half of the wires uninvolved. Repeat twice, if required for the next step to have enough working space.





3. Use Many Ancilla Bits to Finish

For each still-too-large operation, borrow the many uninvolved wires as ancilla bits. Use them to get all the way down to Toffoli-or-smaller gates.





Those three steps will get you all the way from a fully-controlled-not to linearly many Toffoli, CNOT, and single-qubit gates. There's a few implied pieces, like how to merge a control into an increment gate, but they're pretty simple.

(Sorry for the inconsistent style of the diagrams.)