It takes exactly 0 seconds for the MX records to propagate... because DNS records don't propagate.
What you need to think about is how long the TTL for the MX record and corresponding A record are. That will determine how long a DNS client which has already resolved the MX and A record will hold that information in its DNS cache (which would be on the DNS client and its corresponding DNS server).
All DNS clients that haven't already resolved the MX and A record will query your name servers and get the new MX and A record immediately, so no TTL cache delay will occur.
EDIT:
My intention was not to start a semantical debate about the definition of the word propagation and its relation to DNS and without belaboring this point too much longer I'd simply state that only a DNS client that requests info from your DNS zone will get that information. The DNS client lives in a bubble. It knows nothing about your DNS until and unless it asks for it. Even if you consider that a DNS client's DNS server can make the information available to its other DNS clients, it doesn't do so until asked to do so. The DNS info doesn't get propagated or disseminated to any DNS client that doesn't ask for it. Once the TTL expires the information is flushed from the DNS cache, never to be seen or used again unless that client makes a new request. It does nothing else with the information other than hold it in its own cache. Other DNS clients of the same DNS server that query for the same information will get it from the DNS server by asking for it, not by the DNS server propagating or disseminating it.
We can debate whether or not the word propagation, as it's used in relation to DNS, is a loosely defined term with the understanding that we all really mean caching when we say propagation, but at the end of the day it's an incorrect usage of the word, implying a mechanism that isn't employed, and as evidenced by your question, is misunderstood and therefore "propagates" a misunderstanding of how DNS works.
Regardless of what you or I think the word propagation means, its use in the context of your question is incorrect.