I thought IMEI could not be changed. Is it possible here because on a smartphone everything is software defined?
You can generally do this, if you are super technically inclined, and have the right tools for the phone in question. In almost every case, you have to defeat the security on the baseband firmware, because it's embedded as part of the firmware in what's called a "seczone" (contains security data for the phone, which is cryptographically signed, including the carrier lock and IMEI).
Most of the work required to rewrite the IMEI is not actually done by people attempting to be able to rewrite the IMEI; instead, the purpose is to be able to rewrite the carrier lock which happens to be in the same area, so if you have the source code for the tools, or know how to use IDA Pro and read and modify assembly language, you can convert the tool.
This is basically true of almost every Samsung baseband chip firmware, since it has a buffer overflow attack that works against the cryptographic signature check, and then - game over. This is how the Sony, Samsung, and original iPhones carrier lock was busted. For other phones, you can buffer overflow the firmware by using a specially designed chip that pretends it's a SIM chip, and buffer overflows the baseband from the other side of things, rather than from application space. It's probably worth my while to not go into too much detail here.
A non-stupid company that wanted to disincentivize that level of hacking on the baseband - said hacking also being an effective means of modifying the radio tables for the SDR (Software Defined Radio) - would put the carrier lock up in application space, rather than putting it in the baseband firmware in the first place. Most companies, Apple included, have been pretty stupid about their carrier lock implementations, though.
So yeah, the tools exist, mostly because of carrier lock, and the implementation details for the carrier lock being in a stupid location that makes the IMEI rewrite an easy opportunistic target.