The EU has an extensive report on the illegal employment of "third country nationals", by which I think they mean non-EU citizens. They have this summary breakdown of where most illegally working TCNs come from:
The
most common third-country nationalities
identified as illegally employed in the eleven
Member State which provided statistics 2015
were Ukrainians (AT, BG, CZ, EE, FI, LT, SK),
followed by Russians (AT, BG, CY, CZ, EE, FI, LT)
and Chinese (BG, CZ, FI, MT, SK).
But there's no attempt to contrast it (put in context) with illegal work of EU citizens themselves (including those who travel to another member state).
It's interesting that France was not among the countries that provided such detailed stats on the citizenship of the illegally working TCNs, although France did provide stats for the number of employers and TCN workers sanctioned for illegal employment. France was actually the top EU country in the latter category with 1774 illegally working TCNs identified in 2015.
The study also notes that overall
However, there are no estimates on the extent
to which the illegal employment is comprised of
TCNs and nationals of the Member State or EU
nationals and data should be treated with
caution.
There are some numbers for Germany that put the foreign illegal workers in context of illegal work in the country though:
In the first half of 2017, 65,755 investigations into undeclared — illegal — work were started in Germany, a rise of 5 percent over the same period of the previous year, Welt am Sonntag reported, citing a confidential report by the German Customs' Financial Investigation Unit.
Foreign, non-EU, workers found to be working illegally in Germany, recorded as being on "unauthorized stays," increased 28 percent year-on-year to 941 in the same period, according to the report. [...] Most of those working in Germany without a permit come from 10 countries: Ukraine, Albania, Serbia, Vietnam, Bosnia-Herzegovina, Macedonia, Turkey, Kosovo, Moldova and Ghana, it noted.
In some fields like cleaning, baby sitting or gardening, illegal work (though not necessarily that of foreigners) is apparently prevalent in Germany; one estimate was that "somewhere between 75 percent and 83 percent of household workers [were] employed under the table".
An EU-sponsored (but not necessarily EU-endorsed) 2013 report noted that
Of the 490 million people in Europe, more than 25 are foreign. It is estimated that
there are between 5 and 7 million workers without permits in the EU. For them
informal work is the only form of subsistence.
But provides no further breakdown of this latter figure. Clearly, there's also a very large gap between such estimates and the number of TCNs identified as working illegally.
Another study also puts the figure in the millions, but toward the lower end of the other estimate:
European experts estimate that 70 per cent of irregular foreigners are employed (Boswell and Straubhaar, 2004). This would suggest up to 2.7 million irregular workers in the EU-27 labour force of 240 million in 2009, based on Clandestino estimates, making only 1.1 per cent of the EU labour force irregular.
Macron may have been obliquely referencing events like those from a month before (which didn't really make it to well-known Western news media) as reported in a Bulgarian source (in English):
The Bulgarian and the French authorities took down a network for human trafficking and labor exploitation. Three Bulgarians and a French national were detained in France. They organized the trafficking of workers near Lyon. 167 illiterate people from Northeast Bulgaria were hired to pick grapes in France. The group was functioning under the camouflage of a legal business. The people hired by a Bulgarian company were posted to France. They signed job contracts with the Bulgarian company in foreign language without knowing the content of the contracts and were promised EUR 60 per day in wages. Most of their money was appropriated by the Bulgarian company. The money laundering happened through business and investments in French real estate properties.
(French media also covered the case, describing it as a "réseau de travail illégal", i.e. network/gang of illegal work.)
Alas it seems impossible to obtain any statistics on how widespread this phenomenon is regarding even Bulgarian [illegal] workers in France.
As for "travailleur détaché", which I think translates as worker posted abroad, French media covered in 2018 a scandal (that stretched back to 2012) in which some Bulgarian and Romanian companies were sending workers to France but paid them as if they were still working in Bulgaria or Romania, which is/was apparently illegal under EU (and French) law. Again it seems impossible to find any statistics on the magnitude of this kind of problem. (Also, the EU Directive on prohibiting pay below the standards of the host country only dates back to 2014.)
The European Labour Authority which is supposed to monitor these kinds of problems has only been launched in October 2019, and apparently isn't expect to be "fully operational" until 2024 (which I'm not sure what means precisely.) There are however some sectoral reports from Eurofund. One such report, focusing on construction workers notes for instance that
Circumvention of posting regulation was assessed as the main fraudulent practice in the
construction sector in Finland and France. On the contrary, in Spain, this fraudulent practice
is not especially problematic nowadays. [...]
In France, social partners agree to assess the relevance of this fraud, identifying a huge
increase of fraudulent forms of posting of workers in recent years. [...]
The misuse of intra-group posting of workers is becoming a relevant fraudulent practice
according to national authorities. There is a growing tendency among European companies to
post workers within branches of the same company or group. In some cases, the groups
concerned have a genuine European dimension –having subsidiaries in various EU MS-:
conversely, it may occur that a company based in an EU Member State will work directly
with a French client, invoicing for its services through a subsidiary or branch, set up in France
with no employees (letter-box companies) [...]
The
analysis of the declarations by companies of posting of workers (Ministry of Labour,
Commission nationale de lutte contre le travail illégal, “Analyse des déclarations de
détachement des entreprises prestataires de services en France en 2015”, September 2016),
shows the following trends: the number of declaration filled up on the ground of intra-group
mobility has sharply increased since 2011. Furthermore, ‘it is very likely that this volume is
only a partial reflection of the intra-group detachment on the national territory, which is
certainly under-reported”, stresses the Ministry of Labour.,. The share of such intra-mobility
in the total of declarations, increased from 3% in 2012 to 7% in 2015. In 2016, the share of
intra-mobility has increased in 2016 by 8,000 declarations.
They also note that France has been trying to combat the phenomenon
with its Law 786 ("Loi visant à
instituer de nouvelles libertés et de nouvelles protections pour les entreprises et les actifs") (aka the El Khomri law) which (among many other changes) basically made a "Social ID" card compulsory for foreign workers posted to France, although there have been some problems with the implementation of this card system.
The EU rules on pay for posted workers were further tightened in 2018 (going from minimum pay for the host country seemingly to sectorial standards), and the tightened rules will take effect starting from August 2020. So while it may be impossible to get stats how badly abused the system was, it clearly seemed bad enough to elicit some (more) changes. Interestingly, Macron had been pushing hard for this change, even though the number (and even proportion) of posted workers from low-pay countries in France is lower than in Germany.