We all know that if $z=f(x,y)$, then the total derivative of $z$ is given by the formula $\Bbb d z = \dfrac {\partial f} {\partial x} \Bbb d x + \dfrac {\partial f} {\partial y} \Bbb d y$.
My question is: do $x$ and $y$ variables always have to be independent with respect to each other? For example let $f(x,y)=x+y$ where $y=2x$ and hence actually $z=f(x)=3x$.
No, but if $x$ and $y$ is not independent then $dx$ and $dy$ is not independent either. In your example you will have $dy = 2dx$ and the differential form becomes:
$$dz = {\partial f\over\partial x}dx + {\partial f\over\partial y}dy = {\partial f\over\partial x}dx + {\partial f\over\partial y}2dx = 1\cdot dx+1\cdot2dx=3dx$$