The Cm6 chord has a major 6th interval in it simply because the "minor" refers only to the second note; it informs us that the second note is a minor third.
The notation and terminology is such that "minor chord" doesn't simply mean "everything that has a major/minor designation must be minor".
Unfortunately, it is not consistent, either. Or, fortunately, depending on the point of view. It turns out that things are the way they are because compactness of common forms beats consistency.
In this case, the Cm6 means the "Cm" triad, plus a 6th. If there is just an "m", it makes the triad minor.
The confusing thing, perhaps, is that the "default flavor" for a 6th is major, but for a 7th it is minor.
That is to say, if nothing else is written other than the digit 6, it's a major 6th. A minor chord with a minor 6th would be written "Cmm6": a Cm plus a m6.
The opposite default applies to the 7th degree. A 7 by itself is minor, rather than major.
What is worse, the letter M doesn't apply to the triad, but to the 7th degree. Thus C7 means the C triad (i.e. major), with a minor 7th.
There is a certain logic to it nevertheless, which is why you don't really have to think about this. The default triad is major, so you write C for the C major triad, and use an explicit m for the minor triad only. This means that the upper case M never refers to the triad, and the lower case m always does. Given that convention for triads, the rest of it follows. The letter m is occupied by denoting the triad, but the letter M is free, having no use. So the convention is that CM7 denotes the major 7th, and the absence of M, C7, denotes the dominant. The opposite convention wouldn't work that well. If C7 denoted the major 7th chord rather than the dominant, we would have to write CMm7 for the dominant, which is clumsy for such a frequently needed chord (already verbose without any additional voices like 9ths, 11ths and so on, and alterations).
The 6th interval has no such issue: we make it default to major, and that works because it appears often, over either a major or minor triad. If an explicit M had to be written to get a major 6th, then the nice notations like Am6 and C6 would become AmM6 and CM6, or perhaps CMM6. Am6 would still exist, and would denote the much more rare Amm6 chord.
In any case, all the cases not covered by common usage can just use two m's to spell out which triad and which 6th or 7th. The notation being the way it is lends a terse expression to all the chords that come up in the musical traditions to which that notation is tied.
I always build them based on the scale that corresponds to the quality of the chord.
That's your problem; that's not how chords are defined. A C Major chord is exactly the same no matter whether you "select" the notes from the keys of C Major, A Minor, F Major, D Minor, etc. It's even the same if you're playing a piece in C# Major and the composer decided to throw one in for some reason.