How is a new department born?
In all of the cases I have heard of, existing departments split. Sometimes not one, but sometimes faculty from several existing departments split to form a new one. For example, faculty from mechanical engineering, physics, chemistry, and maybe math may form a new department of materials sciences.  Or faculty from math, statistics, computer science, biology, and a variety of engineering departments may form a department of computational science. Oftentimes, such departments are born after there is already a graduate or undergraduate degree that exists in this area and to which the involved faculty members have previously contributed.

In the cases I know of, the initiative has always come from the bottom, not the top. Typically, this has to do with faculty members feeling that there is a critical mass of faculty in a variety of departments to create a new degree program, and they later realize that they may as well build a department around it. The other reason is that the members of such a group may feel that the department they are in does not value their work -- this is, for example, how many statistics and applied math departments started as forks of mathematics departments dominated by pure math faculty who did not appreciate the work or style of the stat or applied math researchers.

In all of these cases, new departments consist of existing faculty. So at least as far as faculty salaries are concerned, this is often not substantially more expensive than the existing structure. Where things get more expensive is that departments typically duplicate support structures as well, such as staff, web site maintenance, etc. But it is not necessarily true that this is "very expensive" as you state.