結論から先に言うと、言語と方言の区別は難しく、定義もあってないようなものです。
大きくいうと、お互いに理解できるかどうかが言語と方言を区別する基準の一つとなっています。
しかし、おっしゃるように言語が異なっていても相互理解が可能である場合もあれば、同じ言語の中でも理解することができない方言もあります。
言語と方言の違いについてですが、
まず一つに、音声や音韻、文法、語彙などによるものがあります。違いが大きければ方言でなく別の言語だというわけです。しかし、中国語の例を見ても分かるように、これは曖昧で、どこまでが許容範囲なのかという明確な線引きはできていません。
二つめは、上であげたような言語内の基準に関わらずに、国家や宗教、民族、伝統などで分けるやり方です。例えばスペイン語とポルトガル語は似ていても国家が違うので別の言語だ、ということです。これも絶対ではありません。例えば英語という一つの言語がイギリスでもアメリカでもオーストラリアでも話されてますから。
言語か方言かという問題は、一つめに挙げた言語内の基準と、二つめに挙げた言語外の基準を組み合わせて判断するのです。それも研究者によってさまざまで、客観的な基準はありません。
世界の言語の総数が確定されないのも、このように言語と方言の区別が非常に曖昧だからです。言語の数は3000だという人もいれば、10000だという人もいます。
例えば、日本人の多くは、沖縄の言葉は日本語の方言であると認識していると思いますが、日本語と琉球語という別個の言語だと考える人もいます。
つまり、言語と方言の明確な違いはない、ということになってしまうのです。