Which one is correct?
Tengo miedo que me echen del trabajo.
Or:
Tengo miedo de que me echen del trabajo.
Which one is correct?
Tengo miedo que me echen del trabajo.
Or:
Tengo miedo de que me echen del trabajo.
As a general rule, to help you identify if you have to write que or de que, just substitute the relative clause with "algo" (literally, "something"):
Tengo miedo algo.
Tengo miedo de algo.
Here we can clearly see that the first sentence is quite ungrammatical, hence the verb needs a de that has to be kept when you switch back to your original sentence:
Tengo miedo de que me echen del trabajo.
If you still don't see it clearly, we can just look for the word in the Diccionario panhispánico de dudas (DPD), although you need to read Spanish for that:
miedo. 1. ‘Temor’. El complemento que expresa la causa del miedo puede ir introducido por a o de.
So the reason for the fear must be introduced in Spanish by the a or de prepositions. So you can say:
Tengo miedo a que me echen del trabajo.
Tengo miedo de que me echen del trabajo.
I would say that I see de more frequently than a, though it depends on the specific sentence. The DPD also says:
Cuando el complemento es una subordinada introducida por que, no debe omitirse la preposición.
So it clearly specifies that you must not omit the preposition even if the reason for the fear is specified by a relative clause.