Its a bit muddy.
I'm assuming you're saying you have something like
theirdomain.com has records (e.g. "A" or "AAAA" pointing to a specific IP for their web service.
yourdomain.com has CNAME records pointing to theirdomain.com (and maybe
www.yourdomain.com has CNAME to theirdomain.com or
www.theirdomain.com).
If so those records say where the main domain goes.
The "MX" is a separate record type. You typically defined that as a name like mailserver.yourdomain.com then have a separate record (usually an "A" or "AAAA") that defines mailserver in the yourdomain.com zone file as a specific IP (which may or may not be the same as the one you're using in base setup for web service as well). It might be a CNAME itself but I've not done CNAMEs for these. The important thing here is you have two separate records. One is the MX that tells people what mail server name to use and another that tells people where to find that mail server name (e.g. by its IP).
Usually if you're using the Registrar's DNS setup they have place where you can update records for yourdomain.com. First you'd want to see if you have an MX record for yourdomain.com their. If so you'd change that entry to point to your mailserver name. If your mailserver name is not in the the Registrar's DNS setup for yourdomain.com then you'd also have to add that record.
How you do that at the Registrar depends on who the Registrar is but the concept is the same.
