I'm not sure what you mean by the "network-served" part. Is this TM drive backing up anything besides the iMac it is connected to? IOW, what is the "network-served" part all about?
As I said, it's an external harddisk that is attached to an iMac in my office, via USB3. The iMac shares the volume on that disk with my MBP, which is connected to that iMac via Thunderbolt 2. The disk is practically idle, the MBP is the only network client. The iMac is idle, too. In short, perfect conditions, network-wise.
Also, how full is that drive? If it is very full this could affect backup times adversely.
It's not substantially fuller than before the El Capitan upgrade, when backups were still fast.
You might also want to run Disk Utility's First Aid on it to make sure its file system is OK.
That was actually the first thing I tried. All fine.
And in case you ask, the logs don't spit out anything suspicious (at least not when filtering for *backupd*). CPU load on the MBP is not suspicously high during the backup. Neither is it high on the target device, be it the iMac or the NAS. Network throughput during backup is low (at least regarding volume - haven't checked packet counts).
After all, Apple has never supported using a NAS as a Time Machine backup drive, so they are under no obligation to make sure any version of OS X works with those devices.
You sound a bit like a lawyer 😉
But seriously, I fully understand that Apple is not obliged to make sure their upgrade does not break stuff they said they didn't support. Still, please understand that it ***** great deal when an OS upgrade turns your hitherto perfectly functional and fast backup solution into a pile of useless junk.
But anyway, as said above, it's unlikely that the problem is some unsupported feature in the network file sharing protocol, since this problem also affects a volume that is shared over the network by an iMac, which IMHO is clearly a supported case.