I believe this restriction comes from the Domain Name System (DNS). A certificate's common_name is treated as a host name, and the error you see comes from the idna library which handles internationalized domain names.
The maximum length of a domain name is 253 bytes, and each label within the domain name can only be 63 bytes. The reason for this limit is the encoding used in DNS, where each label is preceded by a length field in which the upper two bits must be set to zero. (The upper bits are used for compression of domain name suffixes, which may appear multiple times in a DNS query.) The restriction to 253 bytes for the entire domain name comes from the need for an initial length field (1 byte) and a final length field (1 byte, set to zero). The intervening length bytes are represented as periods in the textual representation of a domain name.
So, a common_name that does not include any periods is interpreted as just one DNS label, which may only be 63 bytes long--- this may be fewer characters than 63 if an internationalized domain name is used. The common_name may be up to 253 bytes if you include multiple labels within the name, each label limited to 63 bytes.
best,