*This is a more detailed version of fedja's answer:*

We shall need the following preliminary results:

**Lemma 1:**
Let $\lambda \in \mathbb{S}^1$. Then, the distance of $\lambda$ from $1$ is not greater than twice its distance to the set of non-negative reals.

**Proof of lemma 1:**

Denote $\lambda = a+ib$. Note that $|\lambda-1|= \sqrt{2-2a}$.

**We separate into two cases:**

**$(1)$: $a \ge 0.$**

Since $a \ge 0$, it is clear that $d(\lambda,x_{\ge 0})=|b|$, so

$$2d(\lambda,x_{\ge 0}) \ge |\lambda-1| \iff 2|b| \ge \sqrt{2-2a} \iff 4b^2 \ge 2-2a \iff $$

$$ 2-2a^2=2b^2 \ge 1- a \iff a+1-2a^2 \ge 0$$

This holds since the L.H.S equals $a(1-a)+(1-a^2)$ which is a sum of two non-negative numbers. (Remember $0\le a \le 1$).

**$(2)$: $a < 0.$** In that case $d(\lambda,x_{\ge 0})=1$, so the inequality becomes $2 \ge |\lambda-1|$ which is trivial (The diameter of the unit circle is $2$).

**Lemma 2:**

Let $A_t, \, \,(t\in[0,1])$ be a continuous family of matrices and $K$ a compact set on the complex plane (with a continuous **connected** boundary). If the boundary of $K$ contains no eigenvalues of $A_t$ for all $t\in(0,1)$, then all $A_t$ for $t \in (0,1)$ have the same number of eigenvalues in $K$, which we denote by $d$. Moreover, the number of eigenvalues of $A_1$ is greater than or equal to $d$.

**Proof of lemma 2:**

Let $P_t$ be the characteristic polynomial of $A_t$. Then by the assumption on the eigenvalues of $A_t$, $P_t|_{\partial K} \neq 0$.

Since $A_t$ depends continuously on $t$, and the characteristic polynomial of a matrix depends continuously on its entries, $P_t$ depends continuously on $t$.

Fix $t,t' \in (0,1)$ and assume $t <t'$. We want to show $P_t,P_{t'}$ have the same number of roots in $K$. By the Rouch Theorem, this holds if $$ |P_t(z)-P_{t'}(z)| < |P_t(z)|+|P_{t'}(z)| $$ for every $z \in \partial K$.

Assume by contradiction that for some $z \in \partial K$,$|P_t(z)-P_{t'}(z)| = |P_t(z)|+|P_{t'}(z)| $.

Then $P_t(z)\cdot \overline{P_{t'}(z)} \le 0$. Look at the function $s \to P_s(z)\cdot \overline{P_{t'}(z)}$ defined on $[t,t']$; It is positive at $s=t'$, and non-positive at $s=t$. By continuity, there is some $s \in [t,t']$ such that $P_s(z)\cdot \overline{P_{t'}(z)}=0$, which is a contradiction.

Thus, $P_t$ has $d$ roots in $K$ and $n-d$ roots in $K^c$ for every $t \in (0,1)$.

Since roots of a polynomial depend continuously on its coefficients, and since $K^c$ is open we get that $P_1$ cannot have more than $n-d$ roots in $K^c$: If it would had "too many" roots in $K^c$ then this situation would also be true for some $t<1$, contradiction.

So, the number of roots of $P_1$ in $K$ is at least $d$, as required.

**Lemma 3:**

Let $A_0$ be a normal matrix, $Q$ be an arbitrary non-zero matrix.
Then each *connected component* $K$ of the union of closed disks of radius $\|Q\|_{op}$ centered at the eigenvalues of $A_0$ has at least one eigenvalue of $A_0+Q$ in it.

**Proof of lemma 3:**

Denote the eigenvalues of $A_0$ by $\lambda_1(A_0),...,\lambda_n(A_0)$.
Define $A_t=A_0+tQ$. Note that $A_0$ (and hence $A_t$ for small enough $t$) has an eigenvalue in $\operatorname{int}(K)$.

By lemma 2, it suffices to show that no $A_t$ can have an eigenvalue $\lambda$ on the boundary of $K$.

Let $t \in (0,1)$. Since $\lambda \in \partial K$, it satisfies $|\lambda-\lambda_j(A_0)|\ge\|Q\|_{op}$ **for every $j$**. Since $A_0-\lambda I$ is normal, its singular values are the absolute values of its eigenvalues, so the **minimal** singular value of $A_0-\lambda I$ is greater or equal to $\|Q\|_{op}$. This implies that for any non-zero vector $x$, $$|(A_0-\lambda I)x|\ge \|Q\|_{op}|x|$$

and $$|t| < 1 \Rightarrow |tQx|<|Qx|\le\|Q\|_{op}|x|.$$

So, by the triangle inequality $$|(A_t-\lambda I)x|=|(A_0-\lambda I)x-(-tQx)| \ge |(A_0-\lambda I)x| -|tQx| >0.$$

We have shown $\lambda$ is indeed not an eigenvector of $A_t$.

Note that the last estimate used the fact $t$ is strictly smaller than $1$. This is the reason why we needed a version of lemma 2 where nothing is assumed on the eigenvalues of $A_1$ on $\partial K$.

**Back to the main proposition:**

We want to prove $$(1) \, \, |AB-O_{AB}| \ge c|AB-O_AO_B|$$ for some $1>c>0$.
Let $A=O_AP_A,B=O_BP_B$ be the polar decompositions of $A,B$. Then $$AB=O_AO_B(O_B^TP_AO_B)P_B=O_AO_BXY,$$ where we Denote $$X=O_B^TP_AO_B,Y=P_B \, \text{ (both are symmetric positive definite) }$$

Then $(1)$ becomes:$$ |O_AO_BXY-O_{AB}| \ge c|O_AO_BXY-O_AO_B|=c|XY-I|$$

(The last equality holds whether we use the Frobenius norm, or the operator norm, since both are invariant under multiplication by orthogonal matrices).

Denoting $U_{A,B}=(O_AO_B)^{-1}O_{AB}$, and using again the orthogonal invariance of the norm we get that $(1)$ is equivalent to $$ |XY-U_{A,B}| \ge c|XY-I|$$

Note that $XY$ similar to $X^{1/2}YX^{1/2}$, so **all** its eigenvalues are **real positive**.

Thus, it suffices to prove the following:

**Lemma 4:**

Let $U \in \operatorname{O}_n$,$A \in M_n$ with *positive* eigenvalues. Then $|U-I|_{op} \le 5n|A-U|_{op}$.

**Why lemma 4 implies our required result?**

$$|A-I|_{op} \le |A-U|_{op}+|U-I|_{op} \le (5n+1)|A-U|_{op}$$
Putting $A=XY,U=U_{A,B}$ this becomes:

$$ |XY-I|_{op} \le (5n+1)|XY-U_{A,B}|_{op}$$

Q.E.D

**Proof of the lemma 4:**

Assume by contradiction that $|U-I|_{op} > 5n|A-U|_{op}$.

Since $U-I$ is normal $|U-I|_{op} = \max{|\lambda_i-1|}$ (where the $\lambda_i$ are the eigenvalues of $U$). So, there exists an eigenvalue $\lambda$ of $U$, such that $|\lambda-1|>5n|A-U|_{op}$.

Since $\lambda \in \mathbb{S}^1$ lemma (1) implies that the distance of $\lambda$ from the semi-positive $x$ axis is greater than $2\frac{1}{2}n|A-U|_{op}$.

Now we use lemma 3: Take $A_0=U, Q=A-U$ here and let $K$ be the connected component of the union of disks of radius $|A-U|_{op}$ containing the "faraway" (from the positive real semi-axis) eigenvalue of $U$. Then (according to lemma 3) $A$ has at least one eigenvalue in $K$.

But this is impossible:

Since the eigenvalues of $A$ are real positive, the distance between an eigenvalue of $A$ in $K$, and the faraway eigenvalue of $U$ is at least $2\frac{1}{2}n|A-U|_{op}$. So $\operatorname{diam}(K) \ge 2\frac{1}{2}n|A-U|_{op}$.

However, $K$ is a union of at most $n$ disks of radius $|A-U|_{op}$, thus $\operatorname{diam}(K) \le 2n|A-U|_{op}$ which is a contradiction.

operatornorm, then the constant does depend on the dimension (so, in your notation, $c\approx (\log n)^{-1}$). You seem to care more about the Frobenius norm though. I surmise that it doesn't really make any difference, but am too lazy to try to modify my argument to cover that case now. Let me know if anything is unclear or if you have any other questions :-). $\endgroup$ – fedja Sep 16 '16 at 1:03