You can also refactor that recursion to use tail call optimization.

The cons operator is indeed much more idiomatic in this case, but this is mostly a style preference, there is no performance or behavior implication.
Both will generate the same bytecode when prepending a known number of elements with ++.

Thank you for sharing that article. Super interesting read! Also made me realize my use of lists could be optimized:

My original implementation used appending to create the list:

[proc.(head)] ++ map(proc, tail)

However I could instead use the cons operator to actually form a linked list as it is intended:

[proc.(head) | map(proc, tail)]

It also was redundant in its application of [proc.(head)] and could be simplified for just matching against an empty array.

Better version:

defmodule EnumMap do
  def map(_proc, []), do: []
  def map(proc, [head | tail]) do
    [proc.(head) | map(proc, tail)]
  end
end

EnumMap.map(fn x -> x + 1 end, [1, 2, 3, 4])

It is a very good suggestion as an exercise, but for this particular case which is building a list it might not be the best approach, actually :lists.map/2 (used under the hood by Enum.map/2) is implemented with body recursion:

Also see: Erlang -- The Seven Myths of Erlang Performance.

As somebody new to functional programming, can I ask whether this means simply using an accumulator? Or is there some more idiomatic-Elixir method for this? E.g.

defmodule EnumMapTail do
  def map(proc, list) do
    run_map(proc, list, [])
  end
  defp run_map(_proc, [], acc), do: Enum.reverse(acc)
  defp run_map(proc, [head | tail], acc) do
    run_map(proc, tail, [proc.(head) | acc])
  end
end