How should I say the date I start working: Is "start work date" or "start working date"? I googled to just find out that both are used.
Which one is correct, and why?
Neither of OP's alternatives are acceptable compressed forms of what would normally be referred to as date of starting work in the full form of this compound noun. The most common short form is...
Note that the base noun here is date - modified by another noun start, which is itself modified by the noun work. Most compound nouns involve only two nouns anyway, and if there are more than two they usually all modify the same base noun, but the only grammar involved here is that when a noun is being used "adjectivally" it follows the normal rule for adjectives - it comes immediately before the noun it modifies (even if that modified noun is then used adjectivally to modify another noun that follows).
Some organizations -- say, a personnel or human resources department -- have phrases that they use for things that come up often in their own day-to-day business but don't have a widely used phrase. I've seen "start work date" used by such organizations as a way to refer to the date that someone actually shows up at the job and begins working; it comes up in their work to be distinguished from the day the person was offered the job, the day the person accepted the job, and the day the person left the job, etc., all of which are important when the department is calculating leave, waiting periods, tenure, etc.
In this case, it is acceptable to use the phrase the organization uses, even if they tend to treat it as a noun phrase instead of whatever it would normally have been in regular English usage.
In spoken English at least, the phrase I've heard most (in the UK and US anyway) is a simple, "start date", with context being used to determine whether it's referring to the start date of employment, a project, or some other time period. But I've heard most of the other forms above used from time to time as well.
I don't think strict adherence to rules is too much of a concern here. If the priority is simply to be as idiomatic as possible, and so sound like a native speaker, then the only form I'd avoid from all those mentioned so far, is "start working date".