To address some preliminaries, let $T(a,b)$ be the number of steps taken in the Euclidean algorithm, which repeatedly evaluates $\gcd(a,b)=\gcd(b,a\bmod b)$ until $b=0$, assuming $a\geq b$. Also, let $h=\log_{10}b$ be the number of digits in $b$ (give or take). (Note that in these calculations, by counting steps, we ignore the question of the time-complexity of the $\mathrm{mod}$ function. If we assume it is $O(1)$, then all of the following also applies to the time complexity of the algorithm.
In the worst-case, as you have stated, $a=F_{n+1}$ and $b=F_n$, where $F_n$ is the Fibonacci sequence, since it will calculate $\gcd(F_{n+1},F_n)=\gcd(F_n,F_{n-1})$ until it gets to $n=0$, so $T(F_{n+1},F_n)=\Theta(n)$ and $T(a,F_n)=O(n)$. Since $F_n=\Theta(\varphi^n)$, this implies that $T(a,b)=O(\log_\varphi b)$. Note that $h\approx log_{10}b$ and $\log_bx={\log x\over\log b}$ implies $\log_bx=O(\log x)$ for any $a$, so the worst case for Euclid's algorithm is $O(\log_\varphi b)=O(h)=O(\log b)$.
The average case requires a bit more care, as it depends on the probabilistics of the situation. In order to precisely calculate it, we need a probability distribution. If $a$ is fixed and $b$ is chosen uniformly from $\mathbb Z\cap[0,a)$, then the number of steps $T(a)$ is
$$T(a)=-\frac12+6\frac{\log2}\pi(4\gamma-24\pi^2\zeta'(2)+3\log2-2)+{12\over\pi^2}\log2\log a+O(a^{-1/6+\epsilon}),$$
or, for less accuracy, $T(a)={12\over\pi^2}\log2\log a+O(1)$. (Source: Wikipedia)
In the best case, $a=b$ or $b=0$ or some other convenient case like that happens, so the algorithm terminates in a single step. Thus, $T(a,a)=O(1)$.
If we are working on a computer using 32-bit or 64-bit calculations, as is common, then the individual $\bmod$ operations are in fact constant-time, so these bounds are correct. If, however, we are doing arbitrary-precision calculations, then in order to estimate the actual time complexity of the algorithm, we need to use that $\bmod$ has time complexity $O(\log a\log b)$. In this case, all of the "work" is done in the first step, and the rest of the computation is also $O(\log a\log b)$, so the total is $O(\log a\log b)$. I want to stress, though, that this only applies if the number is that big that you need arbitrary-precision to calculate it.
(This underscores the difference between the mathematician's big-O and the programmer's big-O notation: in the first case, you want the bound to be true $\forall n$, even those $n$ which are so absurdly large that no one can ever write them down or store them in memory, whereas in the second case, programmers are primarily interested in $n\in[0,2^{64}]$, and that's a liberal estimate. For them, it's more important to see the "leading contribution" to the time complexity, and for the Euclidean algorithm, the smaller number drives the difficulty of the calculation by and large.)
You are correct in getting an $O(\log E)$ running time for a single iteration of the algorithm, but you are wrong about needing only $V-1$ iterations.
Remember, Kruskal's algorithm does not add every single edge it encounters to the future spanning tree. An edge is only added if it connects two different components of the forest built so far.
This means that we cannot be sure that we're done after $V-1$ steps; that's just the best case, if we're lucky and the first $V-1$ edges were all usable. In the worst case, all $E$ steps will be necessary: maybe the most expensive edge, the one we'd rather not use until we exhaust all other possibilities, is the only edge connecting two sets of vertices.
This is why the running time is $O(E \log E)$.
(Also, if your analysis were correct, then you still don't get $O(V \log E)$. Don't forget about step 1, which is $O(E)$. The only safe way to combine the two parts of your analysis would be $O(E + V \log E)$; depending on how many edges there are in the graph, either term could be higher than the other. On the other hand, once we put an $O(E \log E)$ bound on the loop's running time, we can ignore the $O(E)$ term.)
Best Answer
The innermost loop runs $\lfloor\frac n2\rfloor$ times. The middle loop runs $\lfloor \log_2(n/i)\rfloor$ where $i$ varies in a geometric progression of common ratio $2$ (hence the number of iterations decreases linearly) and the outer loop runs $\lfloor \log_2(n)\rfloor$ times.
Globally,
$$\frac12\lfloor \log_2(n)\rfloor(\lfloor \log_2(n)\rfloor+1)\left\lfloor\frac n2\right\rfloor$$ executions of the body, which is $\Theta(n\log^2(n))$.