How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?
Based on your comments, I recommend go back to basics and first understand running time, bit-complexity, and the running time for multiplication well.  Focus on that before you try to tackle any of the topics in this post, or you're going to get confused.

Here is a suggested syllabus:


First, study big-O notation.  Understand what it means.  Work through the definitions.  This is well covered in standard algorithms textbooks, so work through that material patiently.  See also, e.g., How does one know which notation of time complexity analysis to use?, How to come up with the runtime of algorithms?.  Try to understand why your "shouldn't this be true no matter how large n is?" question is meaningless (hint: big-O notation relates two functions, not two numbers).
Understand bit complexity as a measure of running time for algorithms that work with large numbers.  See, e.g., Precise runtime of the algorithm to find number of digits in an integer,  Relationship between an integer N and the number of bits n required to represent the integer
Understanding the bit complexity of addition.  This will be a good test whether you understand bit complexity.  See, e.g., Time complexity of addition.
Understand the bit complexity of multiplication.  Understand why it is an open problem how fast we can multiply two integers.  See, e.g., Complexity of multiplication, https://en.wikipedia.org/wiki/Multiplication_algorithm, 
Complexity of a recursive bignum multiplication algorithm, What is the fastest algorithm for multiplication of two n-digit numbers?.
Understand the bit complexity of division and modular reduction.  See, e.g., Complexity of Integer Division, Complexity of taking mod.


If there is any of these steps you are unclear on, ask a question about that specific aspect until you understand it well.  Then, go back and study the material on gcd's.  This background material will probably help you make it further through that material.



Remember that just because there is an algorithm to solve some problem in time $O(f(n))$, doesn't necessarily mean that that is the fastest algorithm to solve that problem.  It doesn't mean that is the fastest that the problem can be solved.  For instance, bubblesort can be used to sort numbers; it has a $O(n^2)$ running time.  That doesn't mean that $O(n^2)$ is the "fastest that numbers can be sorted".