Perishable matter is anything that can deteriorate in the mail and thereby lose value, create a health hazard, or cause an obnoxious odor, nuisance, or disturbance, under ordinary mailing conditions. Mailable perishable matter may be sent at the mailer’s own risk when it is packaged as required and when it can be delivered within appropriate and reasonable time limits to prevent deterioration. Examples of perishable matter include mailable types of live animals, food items, and plants.
I'm going to die on this hill: Cheeses like this are real food. Typically real cheese is one of if not the first ingredient. They are made from cheese, milk, and an emulsifying agent. It's literally cheese sauce with a higher melting point. You can make it yourself it's really easy, you can use non standard cheeses for it like provolone or Gouda, and the only real difference would be in preservatives
When I was younger, we moved around a lot, and as side effect of that, we paid for a storage unit to hold less frequently used stuff. Around the time I started high school, we managed to buy a house, and moved everything from the storage unit into our home. In it there was a picnic basket that I had never seen before. I remember looking inside and finding a horrible smelling bag of "bread" which was actually a black liquid with lumps in it. There was also some individually wrapped cheese slices which visually speaking were indistinguishable from any I could buy in the store today.
TL;DR: Probably not illegal, but I doubt the post office would accept it.
Answering this off-the-cuff with no research, but probably not illegal per se (more of a dick move).
A slice of cheese, wrapped or not, definitely would not make it through the sorting equipment intact, would likely melt in the trucks, and would absolutely stink up the place for the postal workers.
Edit: That said, there are classes of items that are prohibited in the mail, and this may fall under one of those. Like I said, I'm answering w/o any research whatsoever and focusing more on the logistics of it.
At the very minimum, this type of mail would incur the $0.46 non-machinable surcharge because it's smaller than one of the minimum USPS dimensions for postcards, namely that one side has to be at least 5 inches (127 mm exact). You may also have issues with it being too floppy for basic handling by the postal carrier, especially if it was previously left in a warm mailbox.
But perhaps a more practical issue may arise first: will stamps even adhere to the wrapping of a Kraft Cheese single? If you cannot affix postage, that's the most immediate impediment.
I remember seeing that people can write the address on a potato and the USPS will deliver it if it has the right amount of stamps, so I suppose its possible. Definitely not "illegal" but the chances it gets thrown in the trash are high.
It'll be all torn up inside one of the machines, probably rip open the package and create a bunch of plastic shreds, and ruin the day of one of their equipment technicians. USPS is not easy on lettermail, their equipment manhandles it.
It's legal. Which probably means that ICE will show up at your door, break in without a warrant, and deport you to a central American prison because you tried.
Kraft singles have a rather low melting point. I feel like, regardless of whether they take it or not, one warm day while it's in the back of a mail truck somewhere would cause it to liquefy and escape the weird cheese condom.