This really looks like an XY Problem where we are fussing about a tax issue that does not really exist. The real issue is understanding the implications of working 1099 vs W2 and looking at the numbers from the perspective of the worker vs the person hiring. There are several rates we need to keep in mind:
Fully Burdened Rate: This is the hourly rate charged to the end customer if they are paying for you hourly. It is usually feels crazy high because it includes the costs of all the other people in the company you are paying for it is not unusual for it to be a significant multiple of the 1099 rate. In this example lets say it is $250/hour.
Hourly Labor Cost: This is what the person hiring you is working from, it is the budget for what they are willing to pay for the position they are hiring you for. This is how much it costs the contracting company for each hour you work. In our example we could say this is $110/hour.
1099 Rate: In this case all employment expenses are being passed onto you as the worker. There might still be some small admin costs but this is basically the maximal hourly payment you will get. In this case it would be $100/hour.
W2 Rate: As a W2 employee you have significantly more costs associated with you on the company side. This includes taxes payed by the employer like the original question was asking about as well as amortized PTO time, health insurance, 401k, and such. It can be significant in an example from my past this number would look like $58/hour in this example.
Given all that setup we can finally talk about what is going on in this question. First off, the number you are actually negotiating is the hourly labor cost and the manager/hr person/whoever you are negotiating with only cares about that. Normally you don't get to see that number, and in this situation you got a glimpse behind the curtain and saw how they calculate the W2 rate they will pay to match that number.
The relation between 1099 and W2 rates are a function of benefits and company structures so the percentages will very from gig to gig. One gig I took the employer had to pay their part of the health insurance regardless of if I used it. That made the W2 rate much less attractive compared to the 1099 rate. I have also been able to negotiate a higher W2 rate because my wife has great insurance so I could guarantee that I would not use theirs. That employer contribution that was part of the hourly labor cost was then eliminated, and they could give me more money without changing the number they actually cared about.
In this question I really don't believe anything nefarious was going on. You just got to see the labor cost calculations they were building your offer off of. That said you can totally get taken advantage of if you don't know how all the parts interact.
I would strongly suggest that you go into the next negotiation with your own spreadsheet that converts the W2 and 1099 rates on offer into effective dollars in your pocket. There are lots of calculators online that can give you a feel for what to include, in the end you need to use the model that matches your situation.
Edit: The OP is very convinced that this is not an XY problem so I will directly address his comment below:
This answer is a bucket full of red herrings. Again, my question was: whether deducting W2 FICA Employer match (from my pay) is legal from the IRS' perspective. I don't see an answer here.
The answer is that "it depends" and "your accountants will hate you." Generally, your employer can deduct any sort of fees you agree to in your contract; so, the starting point is that you are free to contract and work under those terms.
There are knock on effects that would make it illegal, for instance using this as a way to pay less than minimum wage would not be legal. Not informing you about it or retroactively imposing this as a policy would be illegal.
The accounting implications are also significant, this is just a scheme to give the government more tax money. Lets say you make $100 in a normal W2 situation. You are costing the company $107.65 with their FICA contribution and they are sending $15.30 to Uncle Sam. If you move that $7.65 into your pay then the taxed amount is not $100 but $107.65, so government would get $16.47. That also now means there is still an "unpaid" employer contribution left of $1.17 which if you iterate converges with a total cost of $16.68.
I did that math assuming the employer would be increasing your wage to cover their contribution for simplicity, I am sure it would be going the other way. Regardless, by paying you and then charging you the employer contribution the end result will be a FICA tax bill that is about 1.3% higher.
The other bit of tax implication is that normally the employer portion of FICA is not taxed. But now you will also be taxed on that as income with effectively reduces your income by 7.65 times your marginal rate (say 22%) so that will also increase your taxes by another 1.7% or so.
This scheme results in a tax bill that is $3 more an hour, is non-standard, and complex. To bring this topic full circle this is why I think you asking an XY-problem type question, the way you are suggesting you are being cheated doesn't make any sense financially. It does make perfect sense however if you are looking at the way the company calculates equivalent cost 1099 vs W2 rates.
Summary: Not illegal when negotiated as part of your contract while being financially counterproductive and generally dumb.