The issue of Aristotle's beliefs is somewhat complex, and I will merely link to an article on the Stanford Encyclopedia: The Traditional Square of Opposition.
The answer to the main question depends on the sort of constructive logic we employ. In what is often called "intuitionistic" constructive logic, we have a rule called the "principle of explosion" (also called ex falso quodlibet), which says that if can prove a contradiction then, from this, we can conclude any formula that we wish. This rule is also present in classical logic, but it is not as strong constructively as it is in classical logic, because we do not have excluded middle in constructive systems. Nevertheless, some weaker varieties of constructive logic do not include the principle of explosion.
Suppose we do accept that principle. Here is how to show "All unicorns have wings" in the usual informal constructive style, assuming we know that there are no unicorns. Knowing that there are no unicorns, constructively, means that we have a method to derive a contradiction from any proof of "there is a unicorn".
We next need to think about the constructive meaning of "All unicorns have wings". To prove "All unicorns have wings" constructively means to produce a procedure which, given an object $x$ and a proof that $x$ is a unicorn, produces a proof that $x$ has wings. This is related to the BHK interpretation of constructive logic.
One such procedure is as follows:
- First, suppose we are given a proof that some object $x$ is a unicorn. In particular, we have a proof of "there is a unicorn".
- But we know that there are no unicorns. In other words, we know some proof of a contradiction from "there is a unicorn".
- Therefore, we can derive a contradiction from (1) and (2).
- Finally, we use the principle of explosion, which says in particular that from a contradiction we can conclude "$x$ has wings".
Overall, this procedure gives a proof of "$x$ has wings" from any proof of "$x$ is a unicorn". This means that we can prove "Every unicorn has wings" constructively, if we assume the principle of explosion.
Another approach to this is to ignore the quantifier, and work in propositional constructive logic. Here we assume $\lnot U$ (something is not a unicorn) and want to prove $W$ (that something has wings). So we want to look at the scheme
(\lnot U) \to (U \to W).
This scheme is provable in intuitionistic propositional logic (which includes the principle of explosion), but it is not provable in minimal logic, which is a weaker form of constructive logic without the principle of explosion.
The proof of the identity $(\lnot U) \to (U \to W)$ in intuitionistic logic is actually very simple. $\lnot U$ means $U \to \bot$, where $\bot$ is a symbol for a contradictory statement, and the principle of explosion says we may assume $\bot \to W$. We then obtain $U \to W$ from $U \to \bot$ and $\bot \to W$ by applying the inference rule of hypothetical syllogism, which is constructively acceptable.