I got curious and made some research. I have found an article here that explains exactly this difference.
Apparently, under a legal point of view, there is no real distinction between the two as companies tend to treat one type or the other rather arbitrarily.
There are cases where part-timers work alongside with full-time employees, and others where salaries for example are considered monthly or hourly depending on the type of employment.
However, a more precise distinction says that in job magazines パート is used for women only, and generally indicates married women that are not students up to 49 years old. On the other hand, アルバイト makes no gender distinctions and includes university or short-term college students working on a hourly wage (that are not full-time employed somewhere, are not married and up to 34 years old).
Let me add the original reference:
求人情報誌などのアルバイトとパートの違いの定義は高校生や短大生、大学生などの学生で34歳までの未婚者、正社員ではなく時給で働く者をアルバイトと言い、学生でも正社員でもなく49歳までの女性既婚者をパートと分類しています。
アルバイトは男女とも呼ぶのに対しパートは女性のみと明確に定義されています。
The article goes on with some other insights, and saying that while this is the definition in job magazines, the reality in a corporate environment is quite different. In fact, according to the Labor Standard Act (労働基準法), there is no difference between full-time employee, contractor, part-timer, and arubaito. They are all considered as laborer (労働者).
In the end then, I guess that there is somehow a "general knowledge" kind of difference as stated above. However, this gets more subtle when you get to see it under a legal point of view, maybe without a real clear and distinct definition.